Laimingi bilietėliai

Pradinių duomenų failas:

laimingi.in  

Rezultatų failas:

laimingi.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Jekaterinburgo viešojo transporto administraciją labai erzina faktas, kad keleiviai visaip stengiasi išvengti susimokėjimo už savo kelionę. Visos pastangos (premijos vadovams, konduktorių atlyginimo didinimas, autobusų skaičiaus mažinimas) pasirodė bevertės. Patarėjas, specialiai pakviestas iš Uralo valstybinio universiteto, pasakė, kad asmeniškai jis nemėgsta pirkti bilietėlių, nes retai nusipirktas bilietėlis būna laimingas (bilietėlis yra laimingas, jei pirmųjų trijų skaitmenų suma yra lygi paskutiniųjų trijų skaitmenų sumai). Taigi, sprendimas beveik rastas – reikia spausdinti tik laimingus bilietėlius. Tačiau prieš tai dar reikėtų įsitikinti, kiek tokių bilietėlių su unikaliais numeriais gali būti. Tarkime, jei bilietėlio numerį sudarytų tik du skaitmenys, tai tokių laimingų bilietėlių iš viso būtų dešimt (su numeriais 00, 11, …, 99). Gal su kokiu nors skaitmenų skaičiumi šis laimingų ir nelaimingų bilietėlių santykis yra didesnis? Kas, jei numerį sudarys keturi skaitmenys? Sudėtingi skaičiavimai davė ilgai lauktą rezultatą: šiuo atveju būtų 670 laimingi bilietėlių. O kas, jei skaitmenų būtų šeši arba daugiau?

Taigi, jūs turite išgelbėti Jekaterinburgo viešąjį transportą! Parašykite programą, kuri nustatytų, kiek yra laimingų bilietėlių su duotu skaitmenų numeryje skaičiumi. Beje, skaitmenų ant bilietėlio negali būti daugiau nei devyni.

Pradiniai duomenys

Pradiniuose duomenyse įrašytas teigiamas lyginis skaičius, nedidesnis nei 9 – tai bilietėlio numerį sudarančių skaitmenų skaičius.

Rezultatai

Rezultatuose turi būti įrašytas skaičius tokių bilietėlių, kurių pirmosios pusės skaitmenų suma lygi antrosios pusės skaitmenų sumai.

Pavyzdys

4

670