Zadanie A + B - szkopuł

Question

Witam,

Zacząłem robić zadanie: https://szkopul.edu.pl/problemset/problem/kzUlU--NjB0KKAGvz2es62f8/site/?key=statement

I udało mi się zrobić wybitnie nieoptymalne rozwiązanie za które dostałem 30pkt:

#include <iostream>
#include <string>

unsigned long long strange_add(unsigned long long a, unsigned long long b) {
	std::string s1 = std::to_string(a);
	std::string s2 = std::to_string(b);

	if (s2.length() > s1.length())
		std::swap(s1, s2);

	size_t diff = s1.length() - s2.length();
	std::string result = s1.substr(0, diff);
	s1.erase(0, diff);

	for (int i = 0; i < s2.length(); i++) {
		int x = s1[i] - '0';
		int y = s2[i] - '0';

		result.append(std::to_string(x + y));
	}

	return std::stoull(result);
}

int main()
{
	unsigned long long n;
	std::cin >> n;

	int combinations = 2;
	for (unsigned long long i = 1; i < n; i++) {
		for (unsigned long long j = n; j >= i; j--) {
			if (strange_add(i, j) == n) {
				combinations += i == j ? 1 : 2;
			}
		}
	}

	std::cout << combinations;

	return 0;
}

Ogółem to na początku miałem całkiem inne podejście - chciałem badać kolejne cyfry podanej liczby i dla każdej z nich liczyć możliwe rozwiązania. Zauważyłem, że dla każdej cyfry < 20 liczba możliwości to cyfra+1 (przynajmniej tak mi się wydaje). I kiedy iterując cyfry od końca kolejna to 1 to właśnie robiłem te operacje dla liczby dwucyfrowej zamiast pojedyńczo. Ta technika sprawdza się w wielu przypadkach, np. dla 188 to będzie możliwości dla 8 * możliwości dla 18, czyli 9*19, czyli 171. Ale w pewnych przypadkach to nie działa. Np. własnie dla liczby 112. Powinno być możliwości dla 12 * dla 1, czyli 13*2 co daje 26, a prawidłowa odpowiedź to 50.

Ten sposób psuje się przy kilku jedynkach obecnych w liczbie, np. właśnie dla 112 lub 1111. Bo wtedy nie wiadomo, w przypadku np. 112, czy jako całość uważać 11 czy 12, a może każda cyfra jest odrębna. Jest wiele kombinacji.

Więc w jaki sposób mógłbym znacznie zmniejszyć złożonośc tego algorytmu?

Answer 1

Skoro w tym przykładzie z 112 nie wiadomo czy dzielić na 11 i 2 czy 1 i 12 to może by tak sprawdzić po prostu wszystkie podziały? Zastanów się ile ich maksymalnie będzie

Comments

Może być 11 i 2, 1 i 12, oraz 1 i 1 i 2. Czyli 3 różne kombinacje. Jak na to nie spojrzę to nie da się z tego zrobić 50.

---

Bardziej chodziło mi o to, żeby sprawdzić ile tych podziałów będzie dla dowolnego n. Ja twierdzę, że nie wiecej niż 2^18, dlaczego?

---

Każda cyfra (jeśli moje obserwacje są prawdziwe) ma n+1 podziałów, więc jeśli n < 10^18, to jest max. 18 cyfr. Jeśli każde dwie cyfry to będzie na przemian 1 i 9, to mamy w takiej liczbie 18/2=9 liczb dwucyfrowych (i każda liczba = 19), i każde 19 ma 20 podziałów. Więc 20^9 max. podziałów? Skąd 2^18?

---

Nie bardzo widzę jak 19 ma 20 podziałów, poza tym maksymalna para cyfr jaką jesteśmy w stanie otrzymać to 18. Chodzi o to, że podział można zakodować binarnie. 0 oznacza, że cyfra powstała z normalnego dodania dwóch cyfr (których suma jest <= 9), a 1, że dwucyfrowa liczba powstała z dodania dwóch cyfr (których suma jest >= 10) np.

dla 112 i kodowania 000 mamy podział 1 1 2

dla 112 i kodowania 01 mamy podział 1 12

dla 112 i kodowania 10 mamy podział 11 2

Liczbę kodowań można z góry ograniczyć przez 2^18, choć w rzeczywistości będzie ich mniej.

---

Machnąłem się z tym 1 i 9. Chodziło mi o 1 i 8. Więc byłoby 19^9.

Wygeneruje wszystkie podziały dla podanego n, ale nadal muszę zgodnie z tym co mówi podział (czyli dla 1 szukać dwóch liczb z zakresu (0,liczba zlozona z n[i] oraz n[i+1]) które po zsumowaniu dadzą te konkretną z pozycji n[i], n[i+1], a dla 0 już z mniejszego przedziału bo szukać dwóch liczb z zakresu (0,n[i])). Więc takie rozwiązanie zmniejszyłoby złożoność kodu, ale czy to jest rozwiązanie na 100pkt? A może chodziło Ci o coś innego?

EDIT: w sumie przy takim rozwiązaniu to podziały mi się nie potrzebne, bo w każdej iteracji mogę sprawdzać n[i] oraz liczbę złożoną z n[i] oraz n[i+1] (to drugie tylko jeśli tylko iterując od początku n[i] jest rowne 1). Więc jeśli wspominasz o podziałach, to pewnie nie o to Ci chodziło.

---

To o czym mówisz na początku to jest wzorcówka. Tylko trzeba dopracować szczegóły

---

Jedyne co przyszło mi na myśl, to żeby po wyliczeniu ilosci wszystkich kombinacji, odjac tyle ile mozliwych kombinacji ile sie powtarza dla co najmniej dwoch podzialow. Ide w dobrym kierunku?

---

Nie rozumiem, ale nie trzeba nic odejmować, trzeba będzie mnożyć.

---

Aaaaa, czemu ja zawsze robie takie pomyłki. W pewnym momencie uznałem, że wynik np. 18 może być wynikiem dodawania 17 i 1, 16 i 2 itd. Stąd mi się wzięło 19 kombinacji dla 18 xD Nie wiem skąd taki pomysł w mojej głowie, ale jak się otrząsnąłem to wszystko śmiga i się zgadza. Dzięki !