4. Galaktický volebný chaos vzorové riešenie

10 4

1 0 2 5 6 4

11 3

1 4

16 2

1 0 8 4 2

Hrubá sila

Najpriamočiarejšie riešenie, je riešenie hrubou silou. Skúšame postupne všetky čísla od \(1\) vyššie, až kým nenájdeme také, ktoré spĺňa požadovanú vlastnosť. Rotáciu čísla spravíme jednoducho bez zbytočného prevodu čísla na reťazec tak, že číslo celočíselne vydelíme \(b\), čím z neho odstránime poslednú cifru a pričítame k nemu jeho poslednú cifru – zvyšok po delení \(b\) – vynásobenú aktuálnou mocninou \(b\) takou, aby sa táto cifra dostala na začiatok čísla. Keď číslo, ktoré ideme skúšať, je mocninou \(b\), začíname skúšať o jednu cifru dlhšie čísla, a teda aj mocnina, ktorou násobíme poslednú cifru, sa musí \(b\)-krát zvýšiť.

Časová zložitosť je lineárna¹ od hodnoty hľadaného čísla, čo je vo väčšine prípadov až neprijateľne pomalé.

Lepšie riešenie – zostavíme si rovnicu

Označme si dĺžku hľadaného čísla bez poslednej (rotovanej) cifry \(k\). Hľadané číslo si rozdelíme na dve časti: jadro čísla (celé číslo bez poslednej cifry) označíme ako \(a\) a poslednú – presúvanú cifru ako \(d\). Potom naše číslo má hodnotu \(ba+d\), pretože \(a\) posunieme o cifru doľava a na koniec pripisujeme cifru \(d\). Číslo po rotácii má hodnotu \(b^kd+a\), pretože cifru \(d\) posúvame o \(k\) miest doľava (pred \(a\)). Má teda platiť, že

\[n(ba + d) = b^kd + a\]

V rovnici máme tri premenné, \(a\), \(d\), a \(k\). Ak si zvolíme dve z nich, tretiu budeme vedieť dopočítať. Dopočítať budeme chcieť tú, pre ktorú existuje rádovo najviac možností, teda \(a\). \(d\) má len \(b\) možností a \(k\) je dĺžka čísla \(a\), čo je omnoho menej. Platí

\[a(bn-1) = d(b^k-n)\] \[a = \frac{d(b^k-n)}{bn-1}\]

Vyskúšame teda všetky možnosti pre \(k\) od \(1\) vyššie a pre každé \(k\) vyskúšame všetky cifry \(d\). Ak nájdeme nejaké \(a\), uvedený zlomok musí byť celé číslo a ešte musíme skontrolovať, či má naozaj dĺžku \(k\). Inak ho použiť nemôžeme (nespĺňalo by zadanie).

Čísla generujeme od najkratších, ale nie nutne od najmenších, preto ak aj nájdeme vyhovujúce číslo, musíme ešte doskúšať ostatné cifry pre toto \(k\) a vybrať. Najmenšie hľadané číslo bude to lexikograficky najmenšie (v sústave so základom \(b\)).

Čísla, s ktorými pracujeme, sú veľmi veľké a ak nepoužívame jazyk ktorý s takými vie pracovať, ako napr. Python, potrebujeme si naprogramovať vlastnú aritmetiku.

Časová zložitosť vyzerá byť \(O(lb)\), kde \(l\) je dĺžka hľadaného čísla. Problém ale je, že pracujeme s veľmi veľkými číslami, ktoré nevieme násobiť, deliť či modulovať v konštantnom čase, ale v čase lineárnom k súčinu dĺžok čísel, v tomto prípade lineárnom ku \(k\). Preto časová zložitosť tohto riešenia je \(O(l^2b)\).

Vzorové riešenie – generovanie čísla odzadu

Predstavme si, že poznáme poslednú cifru hľadaného čísla, označme ju \(d\). \(d\) je zvyšok hľadaného čísla po delení \(b\) (základom sústavy). Potom \(n\)-násobok hľadaného čísla bude mať zvyšok \(nd \mathrm{mod} b\) po delení \(b\).

Predposledná cifra sa po presune prvej cifry na koniec stane poslednou. Tá je zvyškom po delení \(b\) nového čísla, teda musí byť rovná \(nd \mathrm{mod} b\).

Takto vieme pokračovať ďalej. Ak poznáme posledných \(k\) cifier, vieme zvyšok čísla po delení \(b^k\). Vieme teda zistiť zvyšok jeho \(n\)-násobku po delení \(b^k\). Po odobratí poslednej cifry sa zvyšných \(k-1\) cifier posunie o jednu pozíciu doprava. Keďže poznáme zvyšok \(n\)-násobku – zrotovaného čísla – po delení \(b^k\), vieme zistiť \((k+1)\). cifru odzadu (ktorá je po rotácii \(k\)-ta).

V podstate vieme určiť posledných \(k\) cifier, ale tých \(k-1\) už poznáme a určili sme ich presne týmto spôsobom.

Celé toto vieme robiť bez potreby vlastnej aritmetiky. V jednom poli si pamätáme už vygenerované cifry a v druhom prenosy z jedného rádu do vyššieho. Keďže násobíme číslom, ktoré je v sústave so základom \(b\) jednociferné, máme len jednociferný prenos.

Navyše, číslom \(n\) nemusíme znovu a znovu násobiť celú známu časť čísla \(b\). To, čo sme si už vynásobili, ostáva stále rovnaké, takže stačí vynásobiť len poslednú pridanú cifru a pripočítať prenos.

Ostáva zistiť, dokedy takto budeme generovať nové a nové cifry. Prestať môžeme vtedy, ak ideme pridať cifru \(d\) (poslednú cifru čísla), pretože ju nemusíme pripisovať ako novú, môžeme využiť tú, ktorá príde z konca čísla. Navyše musí platiť, že práve nemáme žiaden prenos, pretože ten by si vynútil ešte nejaké ďalšie cifry na začiatku.

Treba si dať pozor, či naše vygenerované číslo nezačína nulou. Ak však začína, nemá zmysel pokúšať sa generovať ďalšie cifry. Môžeme si všimnúť, že celý beh algoritmu závisí len od najnovšej cifry, najnovšieho prenosu a poslednej cifry čísla. Práve sme sa dostali do situácie, kedy bude najnovšia cifra \(d\) rovná pôvodnej a prenos je nulový, čo je rovnaký stav ako na začiatku. Celý beh algoritmu by sa ďalej začal periodicky opakovať.

Poslednú cifru síce nepoznáme, ale existuje len \(b\) možností. Vyskúšame teda všetky a najmenšie číslo bude také, ktoré má najmenej cifier a spomedzi nich je lexikograficky (podľa abecedy) najmenšie.

Časová a pamäťová zložitosť

Časová zložitosť tohto riešenia je \(O(lb)\), kde \(l\) je dĺžka hľadaného čísla, pretože už násobíme len čísla, ktoré sa vojdu do obyčajnej premennej (cifry v sústave \(b\), ktoré sú menšie ako \(b\)).

Pamäťová zložitosť je \(O(lb)\), ak si pamätáme všetky vygenerované čísla, ak si budeme pamätať len aktuálne vytvárané číslo a doteraz najlepšie nájdené, bude iba \(O(l)\).