Fişierul intrare/ieşire:plangaciosi.in, plangaciosi.outSursăJunior Challenge 2020
AutorAlexa TudoseAdăugată deJuniorChallenge2020Comisia JuniorChallenge2020
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Plangaciosi

De 1 iunie, Doamna Eraotacude s-a gândit să le organizeze celor K copii de la grădiniţă o surpriză. Ea a cumpărat N torturi, tortul cu numărul i având Ai felii. Ea a aranjat copiii într-un şir, i-a numerotat de la 1 la K (se garantează că ştie să numere până la K) şi după o gândire îndelungată a hotărât cum să împartă dulciurile. Astfel, la fiecare moment de timp, copilul care este primul din rând se va apropia de masa pe care sunt aşezate torturile şi va spune din care tort şi-ar dori să mănânce.

  • Dacă pe masă se află cel puţin o felie din tortul respectiv, Doamna Eraotacude îi va da micuţului o felie din acel tort, iar micuţul se va aşeza fericit la coada rândului.
  • Altfel, dacă pe masă nu se mai află nicio felie din tortul respectiv, micuţul va începe să plângă, drept pentru care va fi numit PlângăciosulNr1. Bineînţeles, într-o fracţiune de secundă, colegii lui îl vor urma, declanşând astfel Corul de Plângăcioşi. În acel moment, Doamna Eraotacude va opri definitiv servirea dulciurilor şi va încerca să oprească Corul de Plângăcioşi. Pentru a face acest lucru, ea trebuie sa îl pună la colţ pe PlângăciosulNr1.

Din motive pur statistice, Doamna Eraotacude vrea să ştie, pentru fiecare copil, pentru câte secvenţe de alegeri va ajunge acel copil să fie PlângăciosulNr1. O secvenţă s1, s2, s3, ..., sp se numeşte secvenţă de alegeri dacă st reprezintă tortul din care s-a luat felia de la momentul t (1≤t≤p-1), iar sp reprezintă tortul din care ar fi vrut să mănânce PlângăciosulNr1. Evident, pentru ca o secvenţă de alegeri să fie validă, este necesar ca la momentul t (1≤t≤p-1) să existe pe masă cel puţin o felie din tortul st, iar la momentul p să nu mai existe pe masă nicio felie din tortul sp.

Date de intrare

Fişierul de intrare plangaciosi.in va conţine pe prima linie N şi K. Pe cea de-a doua linie se vor găsi cele N valori Ai.

Date de ieşire

Fişierul de ieşire plangaciosi.out va conţine o singură linie cu K valori. Cea de-a i-a valoare va reprezenta numărul de secvenţe de alegeri în care copilul i este PlângăciosulNr1 (modulo 1.000.000.007).

Restricţii

  • 1 ≤ N, K ≤ 2000
  • 1 ≤ Ai ≤ 2000
  • A1 + A2 + A3 + ... + AN ≤ 2000
  • Pentru 10 puncte, se garantează că în total sunt cel mult 2 * 106 de secvenţe de alegeri
  • Pentru alte 10 puncte, se garantează că Ai = 1, pentru orice i
  • Pentru alte 30 de puncte, se garantează că N ≤ 40 şi A1 + A2 + A3 + ... + AN ≤ 400
  • Pentru alte 25 de puncte, se garantează că A1 + A2 + A3 + ... + AN ≤ 800

Exemplu

plangaciosi.inplangaciosi.out
2 6
1 2
0 1 3 6 0 0

Explicaţie

Cele 10 secvenţe de alegeri sunt:

  1. 1 1
  2. 1 2 1
  3. 1 2 2 1
  4. 1 2 2 2
  5. 2 1 1
  6. 2 1 2 1
  7. 2 1 2 2
  8. 2 2 1 1
  9. 2 2 1 2
  10. 2 2 2

PlângăciosulNr1 este copilul 2 în prima secvenţă, copilul 3 în secvenţele 2, 5 şi 10, şi copilul 4 în celelalte 6 secvenţe.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?