Fişierul intrare/ieşire:qnp.in, qnp.outSursăAlgoritmiada 2017, Runda 1
AutorAdrian Budau, Andrei Popa, Mihai CalanceaAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Qnp

Luând o pauză de la curăţenie, Harry a invadat problema unui anume roboţel mic şi mereu offline... A găsit partea tehnică gata, dar enunţul lipsă. Aşa că a creat ce vedeţi aici...

În laboratorul lui Dexter se găsesc vrute şi nevrute - printre cele nevrute se află Dee Dee, sora micului geniu. De curând, Dexter a parolat intrarea de la bibliotecă în felul următor: computerul din bibliotecă afişează 11 numere: a0, a1, ... a9 şi K. Cel care vrea să intre în laborator trebuie să introducă al K-ulea număr în ordine crescătoare format din exact a0 cifre de 0, a1 cifre de 1 ... a9 cifre de 9, modulo 109+7. Dexter crede că doar el poate calcula repede răspunsul la M astfel de query-uri. Arătaţi-i că se înşeală, creând un program pe care Dee Dee îl va încărca pe roboţelul ei de spart parole, împrumutat anterior din laborator!

Date de intrare

Fişierul de intrare qnp.in va conţine pe prima linie un număr natural M reprezentând numărul de query-uri. Pe următoarele M linii se vor găsi 11 numere naturale, reprezentând valorile a0, a1, ... a9 şi K.

Date de ieşire

În fişierul de ieşire qnp.out veţi afişa M linii, pe linia i aflându-se un număr natural reprezentând răspunsul la al i-ulea query.

Restricţii

  • 1 ≤ M ≤ 5.000
  • 1 ≤ a0 + a1 + ... + a9 ≤ 70.000
  • 1 ≤ K ≤ 1012
  • Pentru teste în valoare de 20 de puncte, M ≤ 50, a0 + a1 + ... + a9 ≤ 30 şi K ≤ 25000
  • Pentru teste în valoare de încă 20 de puncte, M ≤ 4000 şi a0 + a1 + ... + a9 ≤ 2500
  • Numerele pot începe cu cifra 0.
  • Se garantează că există soluţie.

Exemplu

qnp.inqnp.out
6
1 1 0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 0 0 2
1 1 1 0 0 0 0 0 0 0 1
1 1 1 0 0 0 0 0 0 0 2
1 1 1 0 0 0 0 0 0 0 5
1 2 0 0 0 0 0 0 0 0 2
1
10
12
21
201
101
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?