Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | frumusete.in, frumusete.out | Sursă | ONIS 2014, Runda 1 |
| Autor | Teodor Plop | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.425 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Frumusete
Cui nu îi plac numerele frumoase? Fie un număr N, în baza 10. Definim gradul de frumuseţe al lui N ca fiind numărul de secvenţe de lungime 2 pline de 1 existente în scrierea sa în baza 2. De exemplu:
- 11 (10) = 1011 (2), deci gradul de frumuseţe al lui 11 este 1.
- 27 (10) = 11011 (2), deci gradul de frumuseţe al lui 27 este 2.
- 15 (10) = 1111 (2), deci gradul de frumuseţe al lui 15 este 3.
Se dau T - numărul de teste, iar pentru fiecare test două numere naturale, K şi N. Pentru fiecare test, să se răspundă la următoarea întrebare:
- Câte numere naturale X, 1 ≤ X ≤ N, au gradul de frumuseţe egal cu K?
Răspunsul se cere modulo 666013.
Date de intrare
Fişierul de intrare frumusete.in conţine pe prima linie numărul natural T. Pe fiecare dintre următoarele T linii se vor găsi două numere naturale, K şi N, având semnificaţia din enunţ. Pentru că suntem în perioada sărbătorilor, numărul N vă este dat în baza 2.
Date de ieşire
În fişierul de ieşire frumusete.out se vor găsi T linii, pe linia i găsindu-se răspunsul pentru testul i.
Restricţii
- T = 20.000
- 1 ≤ K ≤ 1000
- 1 ≤ N < 21000
Exemplu
| frumusete.in | frumusete.out |
|---|---|
| 3 3 11111 4 1010101 0 1000 | 2 2 6 |
Explicaţie
...
