Spoj - zadanie Sumy ( pomoc w znalezieniu błędnej odpowiedzi )

Question

( uwaga, kod zadania )

Witam, treść zadania wszystko tłumaczy. Oczywiście nie chodzi o to że mi się nie chce a wy macie poszukiwać błąd w moim wykonaniu zadania... Już wiele razy sprawdzałem i wychodzą mi dobre wyniki z dobrą kolejnością. Jednak życie nauczyło mnie że jak coś się dzieje to Spoj mnie dobrze informuje a problemy są wyłącznie z mojej winy, więc się staram już tak nie oburzać ;) Wiem że jak więcej osób zerknie to może ktoś coś znajdzie...

treść zadania -> https://pl.spoj.com/problems/PTSUMY/

stronka z wynikami i kodem mojego programu -> https://ideone.com/9OUUPm

Plus jest taki że liczby wejściowe 'n' są 1>=n<=20, więc w linku są praktycznie odpowiedzi na każde możliwe dane wejściowe sędziego.

Ja osobiście błędu się w nich nie doszukałem...

Poniżej lekko wyjaśnię działanie mojego programu:

( przeczytaj funkcje returnCollection() przed wageElements() )

#include <iostream>
#include <vector>

using intc = std::vector<unsigned>;
using sets = std::vector<intc>;

///-----------------------------------------------------------------------------------

void wageElements(intc& acts, sets& res) {
	for (int i = acts.size() - 1; i >= 1; --i) { //dla wszystkich elementów zbioru 
		while (!(acts[i-1] >= (acts[i]-1))) { // równoważymy ( od obecnego zbioru odejmujemy jeden i dodajemy jeden do tym co jest wcześniej ), robimy to do puki różnica między eleemntami będzie mniejsza lub równa jeden 
			acts[i] -= 1;
			acts[i - 1] += 1;

			if (i > 1) { //jeżeli kolejność jest leksykograficzna to dodajemy zbór do kolekcji zbiorów 
				if ((acts[i - 1] >= (acts[i] - 1)) && (acts[i - 2] >= (acts[i - 1] - 1)))
					res.push_back(acts); //[*] 
			}
			else //jeżeli pracujemy na elemencie drugim to zakładamy poprawną kolejnoość leksykograficzną 
				res.push_back(acts); //[*]
		}
	}
}

///------------------------------------------------------------------------------------

sets returnCollection(unsigned n) { //zwraca wszystkie możliwe zbiory
	sets res; //wektor ze zbiorami 
	intc acts(n, 1); //zbiór na którym działamy i go po czasie zmieniamy ( aktualna przestrzeń pracy )

	bool wasAdd{ false }; //by dwa razy czegoś nie dodać do wyjściowego wektora zbiorów, symbol [*] 

	while (acts[0]!=n) { //do puki w zbiorze nie będzie tylko jednej liczby równej 'n'

		if(!wasAdd) res.push_back(acts);

		int size = acts.size();
		
		if (acts[size - 2] >= (acts[size - 1] - 1)) { //dodajemy dwie ostatnie liczby zbioru do siebie jeżeli są sobie równe lub różnica między nimi wynosi tylko jeden 
			int sum = acts[size - 1] + acts[size - 2];
			acts.pop_back(); acts.pop_back(); 
			acts.push_back(sum);
			wasAdd = false; //jeszcze nie dodaliśmy tego zbioru 
		}

		else {
			wageElements(acts, res); //jeżeli różnica między ostatnimi liczbami zbioru  wynosi więcej niż 1 to musimy dodać do kolekcji zbiorów wyjściowych postać zrównoważoną ( no bo mamy np dla liczby 4: 1,3 - da się to też zapisać jako 2,2 )  
			wasAdd = true; //ponieważ aktualny zbiór został już w tej funkcji dodany do kolekcji 
		}
	}

	res.push_back(acts); // dodajemy 'n'

	return res;
}

///------------------------------------------------------------------------------------

int main() {
	unsigned t;
	std::cin >> t; //testy
	for (int i = 0; i < t; ++i) {
		unsigned n;
		std::cin >> n; //liczba 1>=n<=20

		auto r = returnCollection(n); // mamy w wektorze wszystkie zbiory liczb naturalnych w odpowiedniej kolejności
		for (const auto& i : r) { //wypisywanie
			for (const auto& j : i) {
				std::cout << j << " ";
			}
			std::cout << "\n";
		}

		std::cout << "\n";
	}
}

Trochę mi szkoda że sam sobie z problemem nie poradziłem, ale co zrobić :/

Z góry dziękuje za pomoc, chociaż są pytania tego typu które przez kilka lat nie uzyskały żadnej odpowiedzi :(

Comments

* pasowało by sprawdzić czy suma wszystkich zbiorów daje prawidłowy wynik, więc rozbudowałem pętle:

for (const auto& i : r) {
			int sum = 0;
			for (const auto& j : i) {
				std::cout << j << " ";
				sum += j;
			}

			if (sum == n)
				std::cout << "-> ZAGADZA SIE";
			else 
				std::cout << "-> COS ZLE";

			std::cout << "\n";
		}

No i wszystko się zgadza, widocznie musi być problem z kolejnością leksykograiczną.

Answer 1

Dla n = 7 na pewno jest źle, bo brakuje przypadków 1 2 4,  1 2 2 2,  1 3 3  i  1 6.

Może spróbuj skorzystać z faktu, że odpowiedź dla n jest częścią odpowiedzi dla n+1

Comments

returnSets(n, 1, s)

Tyle. Możesz jeszcze uprościć trochę kod ;)

---

Nie za bardzo rozumiem :/, że tak mam wywoływać następną funkcje czy to mam wywołać kiedy spełni się warunek oznaczony jako komentarz, czy takie parametry zwiastują konieczność przerwania poszukiwania niewłaściwego zbioru... ?

---

W poprzednim kodzie miałeś pierwsze wywołanie takie:

returnSets(n, n, c)

Reszta kodu będzie dobrze działać. Warunek oznaczony komentarzem jest dobry.

---

Że ja tego nie zauważyłem... Może przez chorobę i nieprzespaną noc ;)

Teraz to wszystko tylko jeszcze raz przeanalizować i zrefaktoryzować.

Nawet nie wiesz jak jestem wdzięczny

Pierwszy raz problem na SPOJ zajął mi 4 dni. Kiedyś robiłem nawet kilka zadań dziennie jak mi się nudziło, takie tam łamigłówki...

To jednak jest już wyższy poziom, nie chce mi się myśleć co mnie czeka na w kategorii trudne. Ale cofając się w czasie to przy pierwszych zadaniach miałem podobne problemy w kategorii łatwe, z czasem dla człowieka zadania z którymi kiedyś nie mógł sobie poradzić stają się łatwe. Często miałem problemy z którymi na śmierć nie mogłem sobie poradzić, nie miałem nawet pomysłu na sensowny algorytm, aż pewnego dnia na nudnej lekcji w szkole coś mi wpadło samo do głowy i nie mogłem się doczekać aż w domu zaimplementuje pomysł zanim go zapomnę :)

Trochę mi szkoda że z tym zadaniem większość to miałem podpowiedziane a sam niewiele zrobiłem, jednak w sumie po to są fora i inne pomoce żeby z nich korzystać.

Ustaw pierwszy swój post jako odpowiedź to dam naj

Jeszcze raz dziękuje i serdecznie pozdrawiam.

---

Cieszę się, że mogłem pomóc. Z początku chciałem dać tylko małą uwagę, ale wyszło jak wyszło - nie będę zawracał głowy moderatorom  Pozdrawiam!