| Fişierul intrare/ieşire: | narbi.in, narbi.out | Sursă | Junior Challenge 2012 |
| Autor | Radu Stefan Voroneanu | Adăugată de |  Junior Challenge •juniorc |
| Timp execuţie pe test | 0.55 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Narbi
Pe planeta Narb se afla o comunitate de mici vietati de nici 10 cm inaltime numiti narbi. Cu ocazia unui eveniment inca necunoscut, narbii au organizat o intrecere speciala pentru a isi masura fortele. La intrecere participa N narbi numerotati dupa ordinea in care acestia intra in competitie, de la 1 la N. Cand un narb cu numarul de ordine i intra in competitie, acesta spune organizatorilor un numar natural Xi. Organizatorii vor scrie pe o foaie toate numerele de la 1 la Xi transformate in baza 2 lipite unul de celelalt. Punctajul acestui narb este reprezentat de numarul de aparitii a cifrei 1 in acest sir, pe care il vom nota cu Ri. Spre exemplu daca un narb a ales numarul 4 atunci organizatorii vor obtine sirul 11011100, deci punctajul este 5. Datorita competitiei aprige intre acestia, fiecare narb va dori sa obtina un punctaj mai mare decat narbul anterior, deci va alege un numar mai mare decat acesta. Din motive organizatorice s-a convenit ca pentru toti narbii Xi = Xi-1 + (Ri-1 mod 16) + 1. In compensatie, primul narb are dreptul sa aleaga orice valoare X1.
Mai marele conducator al narbilor Ibran are un fiu in aceasta competitie si doreste sa ii afle punctajul, insa nu ii stie numarul de ordine. Tot ce stie despre acesta este ca se afla printre ultimii K concurenti. De aceea el va cere o lista cu punctajele ultimilor K concurenti dupa numarul de ordine.
Date de intrare
Fişierul de intrare narbi.in va contine pe prima linie 3 numere naturale N, K, X1, reprezentand numarul de concurenti, lungimea listei ultimilor concurenti si X1 numarul natural ales de primul concurent.
Date de ieşire
În fişierul de ieşire narbi.out va contine K linii. Pe linie cu numarul de ordine i se afla un numar natural RN-K+i reprezentand punctajul obtinut de concurentul N-K+i.
Restricţii
- 1 ≤ N ≤ 16 000 000
- 1 ≤ K ≤ min(1000, N)
- 1 ≤ X1 ≤ 100
- x mod y reprezinta restul impartirii lui x la y
Exemplu
| narbi.in | narbi.out |
|---|---|
| 2 2 4 | 5 17 |
Explicaţie
Primul narb alege numarul 4. Va obtine secventa 11011100 deci 5 puncte. Al doilea narb alege numarul 10 (4+5+1) si obtine secventa 11011100101110111100010011010 si deci punctajul 17.
