5. Všetko so všetkým súvisí vzorové riešenie

4

4

11

209

81

999999999

Asi prvá vec, ktorú si všimneme, je, že hľadané číslo bude deliteľné číslom \(n\), ktoré sme dostali na vstupe. Tu sa nám črtá prvé riešenie, ktoré jednoducho vyskúša všetky násobky čísla \(n\) a vypíše prvý, ktorý má ciferný súčet rovný \(n\).

Výsledné číslo musí mať aspoň \(\frac{n}{9}\) cifier, a takých čísel je \(10^{\frac{n}{9}}\).

Z nich každé \(n\)-té je deliteľné \(n\), čiže toto riešenie skúša exponenciálne veľa možností. Keďže výsledok môže obsahovať aj nuly, nemáme žiadny horný limit na dĺžku hľadaného čísla, takže tento program môže bežať dokonca ľubovoľne dlho. Poďme teda nájsť lepšie riešenie.

Vcelku dobrý nápad vyzerá byť generovanie hľadaného čísla postupne cifru po cifre. Budeme to robiť zľava doprava, teda od najvýznamnejších číslic k najmenej významným. Pozrime sa na to, čo sa stane, keď k nejakému číslu \(m\) s ciframi \(c_1c_2 \dots c_k\) pripíšeme na koniec cifru \(d\) a dostaneme tak číslo \(c_1c_2 \dots c_kd\). Jeho ciferný súčet sa zvýši o \(d\). Zároveň sa už nikdy neskôr nemôže znížiť, keďže všetky cifry sú nezáporné. Zaujímavé je, čo sa stane s jeho zvyškom. Pri pripísaní cifry na koniec čísla sme všetky cifry posunuli o jedno miesto doľava, čo zodpovedá vynásobeniu desiatimi a napokon sme pričítali cifru \(d\). Hodnota nového čísla je tak \(10m+d\).

Teraz si uvedomme, že pri skúmaní deliteľnosti nás vlastne až tak nezaujíma samotné číslo \(m\), stačí nám poznať jeho zvyšok po delení \(n\), označme ho \(z\). Ten sa pripísaním cifry \(d\) zmení na \((10z+d) \,\mathrm{mod}\, n\).

Našu úlohu si tak vieme previesť na prehľadávanie grafu, kde každý vrchol reprezentuje číslo, ktoré máme aktuálne napísané, a každá (jednosmerná) hrana reprezentuje pripísanie číslice na koniec čísla. Samotné napísané čísla si však pamätať nechceme, keďže sú príliš dlhé. O každom takomto čísle nám stačí pamätať si jeho ciferný súčet a jeho zvyšok po delení \(n\).

Na začiatku máme napísaný prázdny reťazec cifier, ktorý má ciferný súčet \(0\) a zvyšok tiež \(0\) (pretože keď napíšeme cifru \(d\), dostaneme zvyšok \(10 \cdot 0+d=d \,\mathrm{mod}\, n\)). K tomuto prázdnemu reťazcu teraz budeme pripisovať nejaké cifry, čo v tomto poňatí znamená nejaké presuny po hranách. Nakoniec sa chceme dostať do stavu s ciferným súčtom \(n\) a zvyškom \(0\).

Na prehľadanie grafu použijeme prehľadávanie do šírky (BFS). Na začiatku si do prázdnej fronty vložíme počiatočný stav (ciferný súčet aj zvyšok rovné \(0\)). Postupne vyťahujeme z fronty nové stavy a ku každému skusíme pridať každú cifru. Zo stavu so súčtom \(s\) a zvyškom \(z\) sa cifrou \(d\) dostaneme k súčtu \(s+d\) a zvyšku \((10 \cdot z+d)\,\mathrm{mod}\, n\). Ku každému stavu si tiež pamätáme, odkiaľ a s akou cifrou sme sa doň dostali, aby sme vedeli spätne zrekonštruovať vytvorené číslo. Ak nájdeme stav, ktorý má rovnaký ciferný súčet aj zvyšok, ako sme už videli, tento stav nebudeme skúmať znova (je to ten istý vrchol grafu).

Na konci programu pomocou zapamätaných spätných liniek vytvoríme hľadané číslo po jednotlivých cifrách. Treba mať na pamäti, že toto číslo dostaneme odzadu, takže ho pred výpisom musíme ešte otočiť.

Zadanie však od nás chce, aby sme našli najmenšie možné číslo, nie ľubovoľné. Tu je dôležité, že sme použili BFS. Ukážeme, že tento algoritmus našiel naozaj najmenšie možné číslo. BFS nájde cestu s najmenším počtom hrán, teda dostaneme číslo s najmenším počtom cifier (čo hrana, to cifra). Najskôr spracúvame stavy s jednou napísanou cifrou, potom s dvomi, tromi atď. Tiež je dôležité spracúvať hrany idúce z jedného vrcholu v poradí podľa pripísanej cifry od \(0\) do \(9\). Spomedzi rovnako dlhých čísel sa tak vždy dostane menšie číslo vo fronte pred väčšie. Ak dve čísla začínajú rovnako a líšia sa len v poslednej cifre, potom číslo s menšou poslednou cifrou bude vo fronte skôr. Ak sa rovnako dlhé čísla líšia skôr ako v poslednej cifre, potom začiatok (bez poslednej cifry) menšieho sme vytiahli z fronty skôr, a tak všetky čísla, ktoré vzniknú z neho, sa dostanú do fronty skôr a usporiadanosť čísel vo fronte sa zachová. Stavy teda spracúvame v poradí od najmenšieho napísaného čísla k väčším, ale tieto čísla v pamäti nedržíme, každý stav reprezentujeme len dvojicou čísel – ciferný súčet a zvyšok.

Uvažujeme iba ciferné súčty menšie alebo rovné \(n\) a existuje \(n\) rôznych zvyškov po delení \(n\), máme teda \(O(n^2)\) stavov (vrcholov grafu), do ktorých sa vieme dostať. V každom stave máme \(10\) možností, akú cifru pripísať, teda z každého stavu ide \(10\) (konštantne veľa) hrán. Časová zložitosť prehľadavánia je teda \(O(n^2)\), pamäťová je rovnako \(O(n^2)\).