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?
