iepuras

Time limit: 0.07s Memory limit: 64MB Input: iepuras.in Output: iepuras.out

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ădure nn 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ță

Să se scrie un program care rezolvă următoarele cerințe:

  1. Pentru fiecare dintre cele nn 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 nn 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 CC. Acesta poate avea valorile 11 sau 22 și reprezintă cerința problemei. Cea de-a doua linie a fișierului de intrare conține un număr natural nn reprezentând numărul de ouă roșii pictate de Skippie. Fiecare dintre următoarele nn linii ale fișierului de intrare conține câte un număr natural nenul reprezentând numerele pictate de iepuras, pe cele nn ouă roșii.

Date de ieșire

Fișierul de ieșire iepuras.out va conține nn 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 CC.

Restricții și precizări

  • 1C21 \leq C \leq 2;
  • 1n100.0001 \leq n \leq 100.000;
  • numerele pictate de iepuraș sunt mai mici sau egale cu 101810^{18}
# Punctaj Restricții
1 16 C=1C = 1, n=1n = 1, numerele pictate 109\leq 10^9
2 24 C=1C = 1, 1<n1051 < n \leq 10^5, numerele pictate 109\leq 10^9
3 24 C=2C = 2, 1n1001 \leq n \leq 100, numerele pictate 2 000\leq 2 \ 000
4 36 C=2C = 2, 100<n105100 < n \leq 10^5, numerele pictate 1018\leq 10^{18}

Exemplul 1

iepuras.in

1
2
121
33343

iepuras.out

33
77

Explicație

Se rezolvă cerința 11. Sunt 22 ouă pictate (n=2n = 2). Pentru primul ou, pictat cu numărul 121121:

  • cel mai mare număr natural cu cifre distincte format cu toate cifrele distincte ale numărului pictat este 2121;
  • cel mai mic număr natural cu cifre distincte format cu toate cifrele distincte ale numărului pictat este 1212.
    Deci suma celor două numere este 3333 (21+12=3321 + 12 = 33).

Pentru al doilea ou, pictat cu numărul 3334333343:

  • cel mai mare număr natural cu cifre distincte format cu toate cifrele distincte ale numărului pictat este 4343;
  • cel mai mic număr natural cu cifre distincte format cu toate cifrele distincte ale numărului pictat este 3434.
    Deci suma celor două numere este 7777 (43+34=7743 + 34 = 77).

Exemplul 2

iepuras.in

2
2
123
191

iepuras.out

22
39

Explicație

Se rezolvă cerința 22. Sunt 22 ouă pictate (n=2n = 2). Pe primul ou este scris numărul 123123 iar pe al doilea ou numărul 191191.
Cifra de control a numărului 123123 este 66 (1+2+3=61 + 2 + 3 = 6). Numărul de apariții ale cifrei 66 în scrierea a tuturor numerelor naturale mai mici sau egale cu 123123 este 2222.
Cifra 66 apare în scrierea numerelor: 66, 1616, 2626, 3636, 4646, 5656, 6060, 6161, 6262, 6363, 6464, 6565, 6666, 6767, 6868, 6969, 7676, 8686, 9696, 106106, 116116 de 2222 de ori.
Cifra de control a numărului 191191 este 22 (1+9+1=111 + 9 + 1 = 11; 1+1=21 + 1 = 2). Numărul de apariții ale cifrei 22 în scrierea tuturor numerelor naturale mai mici sau egale cu 191191 este 3939.
Cifra 22 apare în scrierea numerelor: 22, 1212, 2020, 2121, 2222, 2323, 2424, 2525, 2626, 2727, 2828, 2929, 3232, 4242, 5252, 6262, 7272, 8282, 9292, 102102, 112112, 120120, 121121, 122122, 123123, 124124, 125125, 126126, 127127, 128128, 129129, 132132, 142142, 152152, 162162, 172172, 182182 de 3939 de ori.

Log in or sign up to be able to send submissions!