Zadanie
Miško by si mal robiť domácu. A ísť postrúhať mrkvu. A už niekedy konečne pozrieť zo záznamu minulotýždňovú prednášku z toho či onoho predmetu. A pozbierať si zo sušiaka prádlo, nech sa dá prať ďalšia várka. A upratať po mačke, ktorá podľa zvuku práve zase na chodbe nagrcala. List povinností pokračuje ďalej a ďalej.
Čím je povinností viac, tým sa do nich Miškovi menej chce. A tak si radšej skúma najnovšiu matematickú zaujímavosť, na ktorú práve narazil: správanie sa ciferných súčinov keď ich robíme opakovane.
Začnime napríklad z čísla 47. Jeho ciferný súčin je \(4\times 7 = 28\). Ciferný súčin čísla 28 je \(2\times 8 = 16\). Ciferný súčin čísla 16 je \(1\times 6 = 6\). No a odkedy sme sa dostali k jednocifernému číslu, už je to nuda: ciferným súčinom jednociferného čísla je ono samo. Ak teda časom dosiahneme jednociferné číslo, celý postup ukončíme.
Niekedy je tento proces rýchlejší, inokedy pomalší. Napríklad číslo \(987\,654\,321\) má ciferný súčin \(9! = 326\,880\) a číslo \(326\,880\) má ciferný súčin 0. Hoci sme začali s oveľa väčším číslom ako v predošlom príklade, skončili sme skôr. A možno sa niekedy stane aj to, že pre nejaký začiatok vôbec nikdy neskončíme na jednocifernom čísle. Alebo žeby sa to predsa len nemohlo stať? O tom Miško zatiaľ nič netuší.
Miško sa rozhodol, že niektorým nezáporným celým číslam priradí skóre, a to nasledovne:
- Každé jednociferné číslo \(n\) dostane priradené Miškom zvolené malé nezáporné skóre \(z_n\).
- Ak má viacciferné číslo \(n\) ciferný súčin \(s(n)\) a číslo \(s(n)\) má skóre \(x\), číslo \(n\) dostane skóre \(x+1\).
Úloha
Na vstupe dostanete hodnoty \(z_0\) až \(z_9\) a tiež cieľové skóre \(c\). Vašou úlohou je nájsť najmenšie nezáporné celé číslo, ktoré má skóre \(c\).
Poriadne si pozrite obmedzenia pre veľkosť vstupu.
Formát vstupu
V prvom riadku vstupu sú čísla \(z_0\) až \(z_9\), v druhom je číslo \(c\).
Formát výstupu
Vypíšte jeden riadok a v ňom jedno číslo – najmenšie nezáporné celé číslo so zadaným skóre.
Obmedzenia a hodnotenie programov
Obmedzenia použité v testoch sme zvolili tak, že v každom teste správna odpoveď existuje (toto nie je úplne zjavné) a navyše vždy platí, že má hodnotu nanajvýš \(10^{18}\) (toto už vonkoncom nie je zjavné ale tiež je to pravda). Tieto predpoklady môžete využiť vo svojich riešeniach.
Sú štyri sady vstupov. Vo všetkých štyroch platí:
- hodnoty \(z_i\) sú z rozsahu od 0 po 3
- ak označíme \(m=\max z_i\), tak každú z hodnôt od 0 po \(m\) má aspoň jedno \(z_i\)
- \(c\) je z rozsahu od 0 po 11
Navyše v prvej sade platí, že odpoveď je nanajvýš 1000, v druhej sade platí, že odpoveď je z rozsahu od 1000 po \(1\,000\,000\) a v tretej sade platí, že všetky \(z_i\) sú rovné nule.
Hodnotenie popisov
Pri hodnotení popisu nezáleží na asymptotickej zložitosti vášho riešenia (keďže všetky čísla na vstupe sú veľmi malé). Ľubovoľné riešenie dosť efektívne na to, aby získalo body za vstupy, môže dostať do 10 bodov za dôkaz toho, že dáva vždy korektný výstup. Posledné dva body sa budú udeľovať za efektívnosť hľadania.
Príklady
Input:
0 1 1 1 1 1 1 1 1 1
2
Output:
11
- Číslo 0 má skóre 0.
- Čísla od 1 po 9 majú skóre 1.
- Číslo 10 má ciferný súčin 0, a keďže 0 má skóre 0, tak 10 má skóre 1.
- Číslo 11 má ciferný súčin 1, a keďže 1 má skóre 1, tak 11 má skóre 2.
Input:
0 0 0 0 0 0 0 0 0 0
3
Output:
39
- Číslo 4 má skóre 0, číslo 14 má ciferný súčin 4 a teda skóre 1, číslo 27 má ciferný súčin 14 a teda skóre 2, no a číslo 39 má ciferný súčin 27 a teda skóre 3.
- Žiadne menšie číslo ako 39 nemá skóre 3.
Input:
2 0 0 0 0 0 0 0 0 1
2
Output:
0
Input:
2 1 2 2 1 1 1 0 1 0
6
Output:
268
Pripomeňme si, akú úlohu riešime. Máme predpísané, aké skóre majú jednociferné čísla. Každé väčšie číslo má skóre o jedno väčšie ako je skóre jeho ciferného súčinu. Našou úlohou je pre dané \(c\) nájsť najmenšie číslo \(n\), ktorého skóre je \(c\).
Pointa celej úlohy
Môže byť správnou odpoveďou číslo \(n = 3\,141\,592\)?
Nemôže. Prečo? Lebo číslo \(1\,123\,459\) má presne tie isté cifry (a teda ten istý ciferný súčin, a teda aj to isté skóre) a je od \(n\) menšie.
A môže byť číslo \(1\,123\,459\) správnou odpoveďou?
Tiež nie. Prečo? Lebo číslo \(23\,459\) má tiež ten istý ciferný súčin a je ešte menšie.
Ale poďme sa na to celé pozrieť od začiatku a pekne pomaly.
Každé číslo má skóre
Keď sa chvíľu pohráme s cifernými súčinmi, pomerne rýchlo si všimneme, že pre ľubovoľné \(n\geq 10\) nám jeho ciferný súčin \(s(n)\) vyjde menší ako \(n\). Je toto naozaj vždy pravda?
Keď už si to všimneme, dokázať to nie je ťažké. Pointa je v tom, že dopísanie ďalšej cifry na koniec čísla zväčší samotné číslo aspoň desaťkrát, zatiaľ čo jeho ciferný súčin len nanajvýš deväťkrát.
To isté ešte raz a poriadnejšie: Majme nejaké \(x\)-ciferné číslo \(n\) ktorého prvá cifra je \(y\). Čo o ňom vieme povedať?
- Hodnota \(n\) je aspoň \(y\times 10^{x-1}\).
- Každá z \(x-1\) cifier nasledujúcich za úvodným \(y\) je nanajvýš 9, takže hodnota \(s(n)\) je nanajvýš \(y\times 9^{x-1}\).
- A teda pre \(x\geq 2\) máme \(n > s(n)\).
No a z toho už by malo byť zjavné, že úplne každé nezáporné celé číslo má korektne definované skóre. (Indukciou podľa \(n\). Ak všetky čísla menšie ako \(n\) majú korektne definované skóre, \(s(n)\) je jedným z nich, a keďže \(s(n)\) má skóre, aj \(n\) má skóre.)
Malé skóre vieme efektívne počítať
Pripomeňme si, že nás zaujímajú len čísla, ktorých skóre je nanajvýš 11. Skóre ľubovoľného čísla \(n\) preto vieme ľahko a efektívne vyhodnotiť: postupne počítame \(s(n)\), \(s(s(n))\), atď., až kým sa buď nedostaneme k jednocifernému číslu (kedy vieme povedať, aké skóre má \(n\)) alebo nespravíme 12 krokov (kedy vieme povedať, že \(n\), z ktorého sme začínali, bude mať určite priveľké skóre).
Neskôr si ukážeme, že ani to počítanie krokov do 12 nie je potrebné robiť, lebo úplne každé číslo do \(10^{18}\) má vždy maličké skóre. Ak ste teda v programe len priamo implementovali počítanie skóre podľa definície, bolo to v praxi rovnako dobré.
Ako vyzerá hľadané riešenie?
Zamyslime sa teraz, čo vieme povedať o správnej odpovedi.
Začneme tým, že skontrolujeme čísla od 0 po 19. Čísla od 0 po 9 majú skóre dané na vstupe a hociktoré z nich môže byť tým, ktoré hľadáme. Čísla od 10 po 19 sú najmenšie viacciferné čísla, ktorých ciferný súčin je od 0 po 9. Aj každé z nich môže byť správnou odpoveďou. Ak sme medzi nimi správnu odpoveď nenašli, vieme, že má hodnotu aspoň 20. Uvažujme teraz o situáciách, kedy je správna odpoveď aspoň 20:
Správna odpoveď nemôže obsahovať cifru 0. Ak by ju obsahovala, mala by ciferný súčin 0, a teda rovnaké skóre ako číslo 10, ktoré je od nej menšie.
Ako už vieme, správna odpoveď musí mať cifry usporiadané od najmenšej po najväčšiu. (Keďže už vieme, že nemáme cifru 0, nemôže nám pri usporadúvaní cifier vzniknúť problém s nulou na začiatku čísla.)
Správna odpoveď následne nemôže obsahovať ani cifru 1. Takéto číslo musí byť aspoň trojciferné (dvojciferné začínajúce 1 sme už pozerali) a keď mu úvodnú cifru 1 zmažeme, tak sa samotné číslo zmenší a jeho ciferný súčin sa nezmení.
Už sme vyhrali?
Áno. Totiž po úvahe, ktorú sme práve spravili, nám ostane tak malé množstvo kandidátov na správnu odpoveď, že si môžeme dovoliť všetkých vygenerovať a skontrolovať. Dokopy je medzi nanajvýš 18-cifernými číslami len pribiližne 1.5 milióna takých, ktorých cifry sú 2-9 a sú usporiadané od najmenšej po najväčšiu.
Implementácia
Samotná implementácia je už pomerne priamočiara. Všetkých \(k\)-ciferných kandidátov na riešenie vieme vygenerovať tak, že vygenerujeme všetkých \((k-1)\)-ciferných a každému na koniec pridáme všetky možnosti pre ďalšiu cifru. Takýmto postupom vieme dokonca všetkých kandidátov generovať v usporiadanom poradí, takže akonáhle narazíme na nejakého so správnym skóre, môžeme si byť istí, že sme práve našli riešenie.
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 62;
<int> base;
vector<long long> answers;
vectorint answers_found;
long long product(long n) {
if (n == 0) return 0;
long answer = 1;
while (n > 0) { answer *= n%10; n /= 10; }
return answer;
}
int f(long long n) {
if (n < 10) return base[n];
return f(product(n))+1;
}
void record_answer(long long number, int score) {
if (score > int(answers.size())) return;
if (answers[score] == INF) {
[score] = number;
answers++answers_found;
} else {
assert( number > answers[score] );
}
}
void go(long long prefix, int add_digits) {
if (add_digits == 0) {
( prefix, f(prefix) );
record_answer} else {
int last2 = prefix % 100;
if (last2 == 22 || last2 == 23 || last2 == 33) return;
int last = prefix % 10;
for (int d=last; d<=9; ++d) {
(10*prefix+d, add_digits-1);
goif (answers_found == int(answers.size())) return;
}
}
}
int main() {
.resize(10);
basefor (int i=0; i<10; ++i) cin >> base[i];
int goal;
>> goal;
cin
.clear();
answers.resize(12, INF);
answers= 0;
answers_found
for (int n=0; n<100; ++n) record_answer(n, f(n));
for (int l=3; l<=18; ++l) for (int d=2; d<=9; ++d) go(d,l-1);
<< answers[goal] << endl;
cout }
Efektívnejšie hľadanie
Množinu kandidátov, ktorých treba prezrieť, vieme ešte ďalej celkom výrazne prečistiť. Napríklad takto:
Číslo \(n\) nebude obsahovať cifry 22 (lepšie je mať jednu štvorku), 23 (šestku), 24 (osmičku) ani 33 (deviatku).
Číslo \(n\) nebude obsahovať cifry 34, lebo lepšie je mať cifry 26 – číslo bude menšie a ciferný súčin rovnaký. Podobne vieme, že \(n\) nebude obsahovať cifry 36 (lepšie je 29), 44 (lepšie je 28), 46 (lepšie je 38) ani 66 (lepšie je 49).
Ak máme v \(n\) cifru 5 tak nemôžeme mať žiadnu párnu cifru – lebo \(s(n)\) bude končiť nulou a potom \(s(s(n))\) bude nula. Medzi zakázané dvojice cifier teda môžeme pridať aj 25, 45, 56 a 58.
Ak do generovania kandidátov pridáme tieto obmedzenia, zredukujeme ich počet z vyššie spomínaného približne 1.5 milióna na iba približne \(9\,000\).
def je_validne(cislo):
= [0]*10
cifry while cislo:
%10] += 1
cifry[cislo//= 10
cislo
if any( cifry[x] >= 2 for x in [2,3,4,6] ):
return False
= [ (2,3), (2,4), (2,5), (3,4), (3,6), (4,5), (4,6), (5,6), (5,8) ]
forbidden_pairs if any( cifry[x] >= 1 and cifry[y] >= 1 for x, y in forbidden_pairs ):
return False
return True
def pridaj_dalsiu_cifru(zoznam):
= []
novy_zoznam for cislo in zoznam:
= cislo % 10
posledna for nova in range(posledna, 10):
if je_validne( cislo*10 + nova ):
*10 + nova )
novy_zoznam.append( cisloreturn novy_zoznam
def generuj_vsetkych_kandidatov():
for n in range(100):
yield n
= list(range(2,10))
kandidati = pridaj_dalsiu_cifru(kandidati)
kandidati for d in range(3,19):
= pridaj_dalsiu_cifru(kandidati)
kandidati for k in kandidati:
yield k
def ciferny_sucin(n):
= 1
odpoved while n: odpoved, n = odpoved * (n%10), n // 10
return odpoved
def skore(n, Z):
= 0
odpoved while n >= 10:
+= 1
odpoved = ciferny_sucin(n)
n return odpoved + Z[n]
= [ int(_) for _ in input().split() ]
Z = int( input() )
c for kandidat in generuj_vsetkych_kandidatov():
if skore(kandidat, Z) == c:
print(kandidat)
break
Checkpoint
Niekde tu by sa dalo vzorové riešenie tejto úlohy ukončiť. My v ňom však ešte nejakú tú chvíľu budeme pokračovať a doplníme ešte nejaké detaily a zaujímavostí navyše.
Počítanie kandidátov
Vyššie sme uvádzali nejaké číselné odhady počtov kandidátov. Tie samozrejme vieme získať tak, že ich naozaj vygenerujeme a spočítame. Vieme ich ale veľmi ľahko spočítať aj pomocou kombinatoriky.
Pozrime sa napríklad na všetky \(d\)-ciferné čísla, ktorých cifry sú od 2 po 9 a sú usporiadané od najmenšej po najväčšiu. Koľko ich je?
Predstavme si, že máme premennú, v ktorej je na začiatku cifra 2, a dve rôzne inštrukcie: inštrukcia +
zväčší hodnotu v premennej a inštrukcia p
ju vypíše.
Pomocou takýchto inštrukcií vieme vyrábať čísla, ktorých cifry sú usporiadané. Napr. postupnosť inštrukcií ++p+pp+++p+
vyrobí číslo 4558.
Pozrime sa na postupnosti inštrukcií, ktoré obsahujú práve sedem inštrukcií +
a práve \(d\) inštrukcií p
. Každá takáto postupnosť vyrobí nejaké \(d\)-ciferné číslo, ktorého cifry sú od 2 do 9 a postupne rastú. A naopak, keď zoberieme ľubovoľné takéto číslo, vieme nájsť práve jednu takúto postupnosť inštrukcií, ktorá ho vyrobí: ideme zľava doprava a pri každej cifre najskôr stlačíme správne veľa +
aby sme premennú nastavili na jej hodnotu a potom stlačíme p
. (Po poslednej cifre ešte doplníme prípadné chýbajúce +
.)
Hľadaných čísel je teda presne toľko isto ako reťazcov dĺžky \(d+7\), ktoré obsahujú \(d\) péčok a 7 plusov. No a takýchto reťazcov je zjavne \({d+7\choose 7}\): vyberieme, na ktorých siedmich pozíciách sú plusy a tým je jednoznačne určené, kde sú péčka.
Asymptotické odhady
Môžeme rozpísať, že \({d+7\choose 7} = \frac{(d+7)(d+6)\cdots(d+1)}{7!}\). Z toho je zjavné, že počet čísel, ktoré majú usporiadané cifry od 2 po 9, závisí od ich dĺžky \(d\) len polynomiálne: je ich \(\Theta(d^7)\).
Keď sme prečistili množinu kandidátov, ostali nám v nej len čísla, ktoré mali nanajvýš po jednej z cifier 2, 3, 4, 6. Navyše buď mali len nepárne cifry (vtedy sú premenlivé len počty cifier 5, 7 a 9) alebo neobsahovali cifru 5 (a vtedy sú premenlivé zase len počty cifier 7, 8 a 9). Podobnou kombinatorickou úvahou dostávame, že čísel dĺžky \(d\) jedného aj druhého typu je len \(\Theta(d^2)\).
Otvorený problém na záver
Najjednoduchšou možnou formou zadania našej úlohy je verzia v ktorej všetky jednociferné čísla majú skóre nula. Pre takýto vstup platí, že skóre čísla udáva jednoducho počet opakovaní operácie “nahraď číslo jeho ciferným súčinom” po ktorom dostaneme jednociferné číslo. Matematici v teórii čísel toto občas nazývajú nie skóre, ale multiplikatívna perzistentnosť čísla.
Ak ste si skúšali svoj program spustiť pre najväčšie platné vstupy, určite ste v jeho výstupoch často narazili na číslo \(277\,777\,788\,888\,899\). Toto je najmenšie číslo, ktoré má multiplikatívnu perzistentnosť 11.
Prečo sme ako najväčšie povolené \(c\) v zadaní zvolili práve 11? O koľko väčšia je vlastne správna odpoveď pre \(c=12\)? Nevieme podobným postupom nájsť aj tú?
Nuž… nielen že nevieme, my vlastne dodnes ani nevieme, či vôbec nejaké takéto číslo existuje. Jeho existencia je otvoreným problémom, ktorý už nejaký ten rok odoláva snahám matematikov. Zatiaľ vieme dokázať, že ak takéto číslo existuje, tak určite musí mať výrazne viac ako \(20\,000\) cifier. Ale skôr si myslíme, že neexistuje. A dokonca pravdepodobne platí ešte podivuhodnejšie tvrdenie: je možné, že už poznáme úplne všetkých kandidátov, ktorí majú multiplikatívnu perzistentnosť väčšiu ako 2. Vyzerá to totiž tak, že keď budeme postupne prezerať väčších a väčších kandidátov, tak nielen že nenájdeme žiadneho s multiplikatívnou perzistentnosťou 12, ale naopak sa veľmi rýchlo minú všetci s multiplikatívnou perzistentnosťou väčšou ako 2.
Prečo je to tak? Intuitívne sa to dá priblížiť nasledovne. Majme nejakého kandidáta s veľmi veľkým počtom cifier. Toto je nejaké pekné systematické číslo, ktorého cifry sú od 2 od 9. Jeho ciferným súčinom je nejaké iné, tiež ešte obrovské číslo. Toho cifry sú však už všelijaké chaotické a skoro vždy niekde medzi nimi vybehne nejaká tá nula. Takže to vyzerá tak, že pre ľubovoľného veľkého kandidáta \(n\) skoro určite platí \(s(s(n)) = 0\).
Posledná známa výnimka má 140 cifier. Presnejšie, 140-ciferné číslo \(v = 2^{25} \times 3^{227} \times 7^{28}\) neobsahuje žiadnu nulu a jeho multiplikatívna perzistentnosť je presne 2. Toto číslo \(v\) je rovné \(s(n)\) pre niekoľko podobne veľkých kandidátov \(n\) ktorí potom majú multiplikatívnu perzistentnosť až 3. Ale od 140 cifier ďalej až po vyše \(20\,000\) cifier už sme prezreli všetky možnosti a sme si úplne istí, že úplne všetky možné \(s(n)\) obsahujú v sebe aspoň jednu nulu.
Zrejme to bude platiť aj ďalej pre ešte väčšie čísla. Hja, ale ako takéto niečo exaktne dokázať?
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.