Rezolvare PBinfo #3769

Pentru că îi plac cifrele, Skippie, iepurașul norocos, a stabilit cum se obține cifra de control a unui număr: se efectuează suma cifrelor sale, apoi suma cifrelor acestei sume, până când suma obținută este un număr format dintr-o singură cifră. Această ultimă cifră, spune Skippie, poartă numele de cifră de control. Skippie a ascuns în păadure n ouă roșii. Pe fiecare ou a pictat câte un număr natural nenul. Iar acum se întreabă care este suma dintre cel mai mare și cel mai mic număr natural care se pot forma din toate cifrele distincte folosite în scrierea numărului pictat. În plus, pentru că lui Skippie îi plac problemele complicate, pentru fiecare număr pictat pe câte un ou el ar vrea să afle și de câte ori apare cifra de control a numărului în scrierea tuturor numerelor naturale mai mici sau egale decât numărul pictat.

Cerința

1. Pentru fiecare dintre cele n numere pictate de Skippie aflați suma dintre cel mai mare și cel mai mic număr natural care se pot forma din toate cifrele distincte folosite în scrierea numărului pictat.
2. Pentru fiecare dintre cele n numere pictate de Skippie aflați de câte ori apare cifra de control a numărului pictat în scrierea tuturor numerelor naturale mai mici sau egale decât numărul pictat.

Date de intrare

Fișierul de intrare iepuras.in conține un număr natural C. Acesta poate avea valorile 1 sau 2 și reprezintă cerința problemei. Cea de-a doua linie a fișierului de intrare conține un număr natural n reprezentând numărul de ouă roșii pictate de Skippie. Fiecare dintre următoarele n linii ale fișierului de intrare conține câte un număr natural nenul reprezentând numerele pictate de iepuras, pe cele n ouă roșii.

Date de ieșire

Fișierul de ieșire iepuras.out va conține n numere întregi, fiecare pe o linie separată. În ordinea apariției numerelor pictate de iepuras în fișierul de intrare, se afișează răspunsurile la cerința C.

Restricții și precizări

• 1 ≤ C ≤ 2
• 1 ≤ n ≤ 100.000
• numerele pictate de iepuraș sunt mai mici sau egale cu 1018

Exemplul 1:

iepuras.in

1
2
121
33343

iepuras.out

33
77

Explicație

Se rezolvă cerința 1. Sunt 2 ouă pictate (n = 2). Pentru primul ou, pictat cu numărul 121:
- cel mai mare număr natural cu cifre distincte format cu toate cifrele distincte ale numărului pictat este 21;
- cel mai mic număr natural cu cifre distincte format cu toate cifrele distincte ale numărului pictat este 12.
Deci suma celor două numere este 33 (21 + 12 = 33).

Pentru al doilea ou, pictat cu numărul 33343:
- cel mai mare număr natural cu cifre distincte format cu toate cifrele distincte ale numărului pictat este 43;
- cel mai mic număr natural cu cifre distincte format cu toate cifrele distincte ale numărului pictat este 34.
Deci suma celor două numere este 77 (43 + 34 = 77).

Exemplul 2:

iepuras.in

2
2
123
191

iepuras.out

22
39

Explicație

Se rezolvă cerința 2. Sunt 2 ouă pictate (n = 2). Pe primul ou este scris numărul 123 iar pe al doilea ou numărul 191. Cifra de control a numărului 123 este 6 (1 + 2 + 3 = 6). Numărul de apariții aale cifrei 6 în scrierea a tuturor numerelor naturale mai mici sau egale cu 123 este 22. Cifra 6 apare în scrierea numerelor: 6, 16, 26, 36, 46, 56, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 76, 86, 96, 106, 116 de 22 de ori. Cifra de control a numărului 191 este 2. (1 + 9 + 1 = 11, 1 + 1 = 2). Numărul de apariții ale cifrei 2 în scrierea tuturor numerelor naturale mai mici sau egale cu 19 este 39. Cifra 2 apare în scrierea numerelor 2, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 32, 42, 52, 62, 72, 82, 92, 102, 112, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 132, 142, 152, 162, 172, 182 de 39 de ori.