Faktoriális

Egy GSM hálózat legfontosabb része az ún. adó-vevő bázisállomás (Base Transceiver Station, BTS). Ezek az adó-vevők általában a cellák közepén helyezkednek el, és (kicsit leegyszerűsítve) minden mobiltelefon a legerősebb jelet kibocsátó bázisállomáshoz kapcsolódik. Természetesen a bázisállomások karbantartást igényelnek, és működésüket rendszeresen műszaki szakemberek ellenőrzik.

Az ACM szakemberei nemrégiben egy nagyon érdekes problémával találták szemben magukat. Meg kellett találniuk a legrövidebb utat, amellyel az összes meglátogatandó bázisállomás érintésével visszajutnak a cég központi épületébe. A programozók több hónapig tanulmányozták a problémát, de nem jutottak eredményre: nem sikerült elég gyors megoldást találniuk. Végül az egyik programozó megtalálta ezt a problémát egy konferenciacikkben. Sajnos azonban az derült ki, hogy ez az ún. „utazóügynök-probléma”, amelyet nagyon nehéz megoldani. N darab tetszőleges sorrendben meglátogatandó bázisállomás esetén ugyanis a megvizsgálandó lehetőségek száma N! (vagyis 1-től N-ig a számok szorzata), amely viszonylag kis N érték esetén is nagyon nagy lehet.

A programozók rájöttek, hogy nincs esélyük a probléma megoldására. Mivel azonban már megkapták a kutatási támogatást a kormányzattól, valamilyen eredményt fel kellett mutatniuk, így hát folytatták a probléma tanulmányozását, mégpedig a faktoriális függvény viselkedésének vizsgálatával.

Ennek keretében definiálták a Z függvényt. Egy tetszőleges N pozitív egész esetén Z(N) az N! decimális ábrázolásmódjának a végén található nullák darabszáma. Rájöttek arra is, hogy ez a függvény nemcsökkenő, vagyis bármely két egész esetén, ha N₁ < N₂, akkor Z(N₁) ≤ Z(N₂), mivel egy pozitív szám megszorzásával nem „veszíthetünk el” egyetlen hátulsó nullát sem, csak újabbak és újabbak jelenhetnek meg. A Z függvény nagyon érdekes, ezért olyan programra van szükségünk, amellyel ennek értékét hatékonyan kiszámíthatjuk.

A bemenet specifikációja

A bemenet első sora egy T pozitív egész számot tartalmaz. Ez az ezt követő számok számát adja meg. Majd T sor következik, amelyek mindegyikében pontosan egy, (a szélsőértékeket is beleértve) 1 és 1 000 000 000 (10⁹) közötti pozitív egész szám (N) helyezkedik el.

A kimenet specifikációja

A kimeneten minden N-hez egyetlen sor tartozik, amely a Z(N) nemnegatív egész értéket tartalmazza.

Példa bemenet

1. 6
2. 3
3. 60
4. 100
5. 1024
6. 23456
7. 8735373

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 0
2. 14
3. 24
4. 253
5. 5861
6. 2183837

letöltés szöveges állományként