2. Zapisovanie trpaslíkov vzorové riešenie

5
2
47
33
750
4247

2
121
66
2664
113322

Hrubá sila

Riešenie hrubou silou vyzerá tak, že postupujeme presne podľa zadania. Postupne si vygenerujeme každú permutáciu cifier zadaného čísla a potom všetky takto vytvorené čísla sčítame. V jazyku C++ sa to dá robiť pomocou funkcie next_permutation(), ktorá generuje ďalšiu permutáciu poľa. V Pythone sa na to dá použiť knižnica itertools. Ak si počet cifier zadaného čísla označíme \(k\), tak takéto riešenie má časovú zložitosť \(O(k!)\) (\(k\) faktoriál) a na testovači by malo získať 2 body.

from itertools import permutations

n = int(input())

for i in range(n):
    c = input()
    print(sum(int(''.join(p)) for p in permutations(c)))

Optimálne riešenie

Najprv potrebujeme zistiť, koľko rôznych permutácií \(k\) cifier vlastne existuje. Ak chceme z \(k\) cifier vyrobiť číslo, dôležité je, v akom poradí ich za seba naukladáme. Na prvé miesto môžeme dať ľubovoľnú z cifier, takže máme \(k\) možností. Na druhé miesto už nemáme \(k\) možností, ale iba \(k-1\). Jedna cifra (aj keď nevieme ktorá) totiž leží na prvej pozícii. Preto máme pre druhé miesto iba \(k-1\) možností, čo je dokopy pre prvé dve miesta \(k\cdot (k-1)\) možností.

Neprekvapivo, pre tretie miesto máme \(k-2\) možností a tak ďalej. Na poslednom, \(k\)-tom mieste máme len 1 možnosť, lebo nám zostala posledná nezaradená cifra. Dokopy máme teda \(k \cdot (k-1) \cdot (k-2) \ldots 2 \cdot 1\) možností. Takýto súčin čísel od 1 po \(k\) zvykneme tiež označovať \(k!\) (\(k\) faktoriál).

Označme si cifry nášho čísla zľava doprava ako \(a_k\ a_{k-1} \ldots a_2\ a_1\). Toto číslo si teda môžeme zapísať aj ako:

\[10^{k-1}\cdot a_k+10^{k-2}\cdot a_{k-1}+\ldots +10^1\cdot a_2+10^0\cdot a_1\]

Je jasné, že to, koľko zaváži daná cifra, je dané aj jej poradím v čísle. Skúsme teraz vypočítať, akú hodnotu pridá cifra \(a_1\) do súčtu všetkých permutácií. Ak dáme cifru \(a_1\) na prvú pozíciu zľava, tak nám do súčtu pridá \(10^{k-1}a_1\). Potrebujeme už len zistiť, v koľkých permutáciách bude \(a_1\) na prvom mieste. Keď si však takýmto spôsobom zafixujeme prvú cifru, ostane nám \(k-1\) cifier, ktoré chceme uložiť na \(k-1\) pozícií. Máme teda \((k-1)!\) rôznych čísel, kedy je \(a_1\) na prvom mieste.

Ak dáme cifru \(a_1\) na druhú pozíciu zľava, bude pridávať do súčtu hodnotu \(10^{k-2}a_1\) a opäť \((k-1)!\) krát, lebo zafixovaním druhej pozície nám opäť ostane \(k-1\) cifier na \(k-1\) pozícií. To isté bude platiť pre ľubovoľné miesto, kam našu cifru \(a_1\) uložíme. Ak toto všetko sčítame, dostaneme celkovú hodnotu, ktorú do súčtu permutácií pridá cifra \(a_1\) a táto hodnota bude:

\[10^{k-1}a_1(k-1)! + 10^{k-2}a_1(k-1)! + \ldots + 10^1a_1(k-1)! + 10^0a_1(k-1)!\]

Po vyňatí \(a_1\) a \((k-1)!\) získame jednoduchší tvar:

\[a_1(k-1)!(10^{k-1}+10^{k-2}+\ldots 10 + 1)\]

Táto istá úvaha však platí aj pre ľubovoľnú cifru, nie len pre \(a_1\). Keďže sú cifry od seba nezávislé, celkový súčet permutácií bude určite rovný súčtu hodnôt, ktoré pridajú jednotlivé cifry. Výsledný súčet všetkých permutácií preto bude

\[a_1(k-1)!(10^{k-1}+10^{k-2}+\ldots 10 + 1) + a_2(k-1)!(10^{k-1}+10^{k-2}+\ldots 10 + 1) + \ldots + a_k(k-1)!(10^{k-1}+10^{k-2}+\ldots 10 + 1)\]

čo môžeme opäť upraviť na oveľa jednoduchší tvar:

\[(a_1+a_2+\ldots+a_k)(k-1)!(10^{k-1}+10^{k-2}+\ldots 10 + 1)\]

Výsledok teda vieme vypočítať ako súčin troch členov. Prvý z nich je súčet cifier, druhý je \((k-1)!\), čo je \((k-1)(k-2)\ldots 1\) a tretí súčet mocnín 10. Každý z týchto členov vieme vypočítať v čase \(O(k)\), čo je teda výsledná časová zložitosť nášho programu. Pamäťová zložitosť je dokonca konštantná \(O(1)\), keďže cifry zadaného čísla vieme počítať postupne jeho delením 10.