20827. Iloczyn cyfr [AL_18_01]

Zadanie:
https://spoj.com/ALGOLIGA/problems/AL_18_01
https://pl.spoj.com/problems/AL_18_01

Skrócony opis problemu:

Dla danej liczby $n$ wypisać minimalną dodatnią liczbę, której iloczyn cyfr jest równy $n$.

Rozwiązanie naiwne:

Zaczynając od 1, przechodzić wszystkie kolejne liczby naturalne i sprawdzając iloczyn każdej z nich, dopóki nie znajdzie się takiej, której iloczyn cyfr jest równy $n$.

Złożoność: $O(n^2 \log n)$, gdyż maksymalna liczba, jaką da się uzyskać dla pewnego $n$ jest rzędu $n^2$, a dla każdej z liczb trzeba obliczyć iloczyn jej cyfr, co ma złożoność $O(d)$, gdzie $d$ jest długością maksymalnej liczby. Owa długość może być wyrażona jako logarytm $n$: $d = \left\lceil \log_{10} \left(n+1\right) \right\rceil$ (np. długość 999 to $\left\lceil\log_{10} \left(999+1\right) \right\rceil = 3$, a długość 100 to także $\left\lceil \log_{10} \left(100+1\right) \right\rceil = 3$ - podstawa 10, bo system dziesiętny).

Rozwiązanie sprytne:

Możemy też zauważyć, że naturalnie wszystkie cyfry muszą być dzielnikami $n$. Co więcej, wszystkie te dzielniki musimy zawrzeć na naszej wynikowej liczbie. Co to oznacza? Ano to, że muszą one być cyframi. To nam znacznie upraszcza zadanie. Wystarczy, że sprawdzimy przez jakie potęgi 2, 3, 5 i 7 dzieli się $n$. Jeśli podzieliwszy $n$ przez te wszystkie potęgi zostanie nam liczba większa od 1, to znaczy, że $n$ ma również co najmniej jeden dzielnik, który nie jest cyfrą - w takim (i tylko takim) przypadku wypisujemy NIE.

Powiedzmy, że mamy już owe potęgi: $2^a$, $3^b$, $5^c$ i $7^d$. Co dalej? Musimy zauważyć, że przede wszystkim interesuje nas zminimalizowanie długości naszej liczby. Trzeba więc połączyć owe liczby tak, by nadal tworzyły cyfry, ale większe. Możliwe są następujące połączenia: $2 \cdot 2 \cdot 2 = 8$, $3 \cdot 3 = 9$, $2 \cdot 3 = 6$ oraz $2 \cdot 2 = 4$. Widzimy, że 5 i 7 nie możemy łączyć, gdyż nie otrzymamy z nich cyfry mnożąc przez cokolwiek.

Teraz musimy uzgodnić, co najpierw łączymy. Cóż, na pewno najpierw łączymy wszystkie 2 w trójki, bo wtedy najbardziej minimalizujemy ilość cyfr. Pozostały nam 3 możliwe połączenia: 3 z 3, 2 z 2 i 2 z 3. Oczywiście jeśli zostały nam same 2 lub same 3, to łączymy je w pary i zostanie nam ew. jedna 2 lub 3. Pytanie co zrobić jeśli mamy i 2, i 3. Skoro długość będzie tutaj taka sama, to co powinniśmy teraz zminimalizować? Pierwszą cyfrę! A zatem, jeśli mamy 2 i 3, to najpierw łączymy 3, by została nam 2, którą damy na początku. Czyli łączymy sobie 3 w pary. Może nam pozostać maksymalnie jedna 3. Oprócz niej mogą nam zostać maksymalnie dwie 2, bo na samym początku łączyliśmy wszystkie 2 w trójki. Jeśli z zestawu 2, 2, 3 mamy zero, jedną lub dwie liczby, to oczywiście wszystko jest jasne. Jeśli jednak mamy cały zestaw, to łączymy 2 z 3 i otrzymujemy liczby 2 i 6.

Podsumowując kroki po kolei:

• wypisz 2, jeżeli po połączeniu wszystkich 2 w trójki zostanie tylko jedna 2 i zero 3 lub jeśli zostaną dwie 2 i jedna 3
• wypisz 3, jeżeli po połączeniu wszystkich 3 w pary zostanie jedna 3 i nie zostanie żadna 2
• wypisz 4, jeżeli po połączeniu wszystkich 2 w trójki pozostaną 2 dwójki i nie zostanie żadna 3
• wypisz tyle 5, ile zawiera $n$
• wypisz 6, jeżeli po połączeniu wszystkich 2 w trójki pozostanie przynajmniej jedna 2 i jedna 3
• wypisz tyle 7, ile zawiera $n$
• wypisz tyle 8, ile trójek 2 zawiera $n$
• wypisz tyle 9, ile par 3 zawiera $n$

Złożoność: $O(\log n)$, bo najwięcej czasu zajmuje nam zliczenie, przez jakie potęgi 2, 3, 5 i 7 dzieli się $n$. Największą ilość dzielników będących cyframi otrzymamy dla samych potęg 2. Dzielników $2^x$ jest dokładnie $x$, więc jeśli przyjmiemy $n = 2^x$, to wyjdzie nam, że $x = \log_2 n$ - stąd logarytm w złożoności.

Algorytm:

int main()
{
        int t, n, two, three, five, seven;

        get(n);
        if(n < 10) // dla cyfr wypisz je same
        {
                print(n ?: 10); // oprócz 0 - dla 0 wypisz 10 (liczba ma być dodatnia)
                continue;
        }
        two = three = five = seven = 0;
        while(n%2 == 0)
                ++two,
                n >>= 1;
        while(n%3 == 0)
                ++three,
                n /= 3;
        while(n%5 == 0)
                ++five,
                n /= 5;
        while(n%7 == 0)
                ++seven,
                n /= 7;
        if(n > 1)
        {
                print(NIE);
                continue;
        }
        if(two%3 == 1 && three%2 == 0 || two%3 == 2 && three%2)
                print(2),
                --two;
        if(three%2 && two%3 == 0)
                print(3),
                --three;
        if(two%3 == 2 && three%2 == 0)
                print(4),
                two -= 2;
        for(int i = 0; i < five; ++i)
                print(5);
        if(two%3 == 1 && three%2)
                 print(6),
                 --two,
                 --three;
        for(int i = 0; i < seven; ++i)
                 print(7);
        for(int i = 0; i < two/3; ++i)
                 print(8);
        for(int i = 0; i < three>>1; ++i)
                 print(9);
}

Rozwiązanie sprytne nr 2:

Autorem tego rozwiązania jest Jarosław Kończak.

Rozwiązanie to jest prawie takie samo jak poprzednie. Różni się tym, że sprawdzamy podzielność przez wszystkie cyfry, zamiast jedynie przez 2, 3, 5 i 7. Dzięki temu nie musimy ich łączyć. Dodatkową zaletą tego rozwiązania jest to, że jeśli liczba jest potęgą 2, to dzielimy ją przez 8, a nie 2 - wykonujemy zatem 3 razy mniej dzieleń w przypadku 8 oraz 2 razy mniej w przypadku 9 i 6. Tak więc zaczynamy sprawdzenie czy $n$ jest podzielne przez 9 i każdą 9 przez którą dzieli się $n$ wrzucamy na początek naszej listy oraz dzielimy $n$ przez 9. To samo robimy z 8, 7, ... i 2. Jeśli pozostała liczba będzie większa od 1, to wypisujemy NIE. W przeciwnym wypadku wypisujemy listę.

Złożoność: $O(\log n)$ - dokładnie tak samo jak w poprzednim algorytmie, jednak tutaj najwięcej dzielników otrzymamy przy potędze 5, więc w poprzednim algorytmie logarytm ma w podstawie 2, a w tym 5. Wychodzi na to, że ten algorytm jest lepszy (im większa podstawa logarytmu, tym mniej operacji), ale czas ma gorszy. Postanowiłem zatem postawić oba algorytmy na równi. Ten jest jednak prostszy w implementacji i trudniej się w nim pomylić.

Algorytm:

int main()
{
        int k = 9, n;
        list<int> result;

        get(n);
        if(n < 10)
        {
                print(n ?: 10);
                return 0;
        }
        while(k > 1 && n > 1)
        {
                while(n % k == 0)
                        result.push_front(k),
                        n /= k;
                k--;
        }
        if(n > 1)
                print(NIE);
        else
                print(result);
}