magnify

Statyba iš nulių

Pradinių duomenų failas:
nuliai.in  
Rezultatų failas:
nuliai.out  
Laiko apribojimas:
2 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Manote, kad nulis – tai niekas? Netiesa! Naudojant tik nulius ir aritmetinius veiksmus, galima užrašyti bet kokį natūralųjį skaičių.

Vien sudėtimi ir daugyba čia neišsiversi. Žinome, kad 0*0=0+0=0. Todėl tenka kviestis šauktuką, kuris žymi faktorialą.

Skaičiaus n faktorialas lygus visų skaičių nuo 1 iki n sandaugai: n!=1*2*3*…*n. Tačiau susitarta, kad nulio faktorialas lygus vienam: 0! = 1. Taigi, faktorialas gali iš tiesų pagelbėti. Pavyzdžiui:

8 = (0! + 0! + 0!)! + 0! + 0! = 3! + 1 + 1 = 2*3 + 2 arba
8 =  \((0!+0!)^{0!+0!+0!}\) = \(2^{3}\)

Pastaba. Skaičiuojant reiškinio reikšmę svarbu žinoti operacijų prioritetus. Jeigu nėra skliaustų, tuomet pirma apskaičiuojamas faktorialas, po to pakeliama laipsniu, tuomet dauginama ir galiausiai sudedama.

Duotas teigiamas sveikas skaičius. Parašykite programą, kuri suskaičiuotų kokiu mažiausiu nulių skaičiumi galima užrašyti duotąjį skaičių, jei konstruojant skaičių iš nulių galima naudoti sudėties, daugybos, kėlimo laipsniu ir faktorialo veiksmus bei skliaustus.

Pradiniai duomenys

Pradinių duomenų faile pateiktas natūralusis skaičius N <= 20000.

Rezultatai

Pirmoje rezultatų failo eilutėje įrašykite vieną skaičių – mažiausią galimą nulių skaičių reiškinyje, kuriuo galima užrašyti skaičių N.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimai
1
1
0!
10
6
\((0!+0!+0!)^{0!+0!}\)+0!=\(3^{2}\)+1=10
12
5
(0!+0!+0!)!*(0!+0!)=3!*2=12
8
5
\((0!+0!)^{0!+0!+0!}\)=\(2^{3}\)=8
© Bronė Narkevičienė