• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie A + B - szkopuł

VPS Starter Arubacloud
0 głosów
180 wizyt
pytanie zadane 30 maja 2023 w C i C++ przez Szyszka Gaduła (3,490 p.)

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?

1 odpowiedź

+1 głos
odpowiedź 31 maja 2023 przez Whistleroosh Maniak (56,900 p.)
wybrane 1 czerwca 2023 przez Szyszka
 
Najlepsza
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
komentarz 31 maja 2023 przez Szyszka Gaduła (3,490 p.)
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.
komentarz 31 maja 2023 przez Whistleroosh Maniak (56,900 p.)
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?
komentarz 31 maja 2023 przez Szyszka Gaduła (3,490 p.)
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?
komentarz 31 maja 2023 przez Whistleroosh Maniak (56,900 p.)
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.
komentarz 31 maja 2023 przez Szyszka Gaduła (3,490 p.)
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.
komentarz 31 maja 2023 przez Whistleroosh Maniak (56,900 p.)
To o czym mówisz na początku to jest wzorcówka. Tylko trzeba dopracować szczegóły
komentarz 1 czerwca 2023 przez Szyszka Gaduła (3,490 p.)
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?
komentarz 1 czerwca 2023 przez Whistleroosh Maniak (56,900 p.)
Nie rozumiem, ale nie trzeba nic odejmować, trzeba będzie mnożyć.
komentarz 1 czerwca 2023 przez Szyszka Gaduła (3,490 p.)
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 !

Podobne pytania

+1 głos
2 odpowiedzi 392 wizyt
pytanie zadane 24 czerwca 2023 w C i C++ przez Szyszka Gaduła (3,490 p.)
+1 głos
1 odpowiedź 159 wizyt
pytanie zadane 7 czerwca 2023 w C i C++ przez Szyszka Gaduła (3,490 p.)
0 głosów
1 odpowiedź 271 wizyt
pytanie zadane 28 maja 2023 w C i C++ przez Szyszka Gaduła (3,490 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...