Zadanie algorytmiczne z wykorzystaniem rekurencji

Question

Cześć, rozwiązuje sobie takie o to zadanie: CSES - Apple Division 

Niestety dla 17 testów otrzymuje dwa błędy, których nie jestem wstanie naprawić gdyż wydaję mi się, że sama idea progamu jak i sam algorytm działa +- poprawnie. Proszę o pomoc i wytłumaczenie dlaczego algorytm nie przechodzi poniższego testu.

test, którego nie przechodzi program:

20
934033764 747013925 113297529 621350044 4858224 896418401 823418019 490285020 811592918 318107753 122431099 971962557 68572395 269437889 506050802 903504371 908615271 406858603 39392057 816479349

#include <iostream>
#include <vector>
#include <cmath>

long long int min = 1000000000;

void appleDivision(long long int w1,long long int w2, std::vector<long long int> p, int i) {
	if ((int)p.size() == i) {
		long int s = abs(w1 - w2);
		if (s < min) min = s;
		return;
	}
	
	appleDivision(w1 + p[i], w2, p, i + 1);
	appleDivision(w1, w2+p[i], p, i + 1);
}

int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0); std::cout.tie(0);
	
	
	int n;
	std::vector<long long int> p;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		std::cin >> a;
		p.push_back(a);
	}

	appleDivision(0, 0, p, 0);
	std::cout << min << '\n';

	return 0;
}

 

Answer 1

OK, to dość subtelna różnica, ale to chyba to:

long int s = abs(w1 - w2);

Zamień abs na std::abs.

"gołe" abs pochodzi z C, tam funkcja działała tylko na intach bo nie było przeładowywania funkcji. W związku z tym, konwersja na inta gubi Ci duże liczby. std::abs ma normalne przeładowanie dla long long.

Comments

Pomogło, dzięki wielkie  To od razu rozwiązuje mój problem z innego zadania, gdzie dla ogromnych liczb program zwracał błędne wartości. Nie wpadłbym, że abs jest temu winien...