| 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, 0 ≤ 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
- 0 ≤ K ≤ 1000
- 0 ≤ N < 21000
- Vă recomandăm să folosiţi gets pentru a citi numerele din fişierul de intrare şi nu cin.
Exemplu
| frumusete.in | frumusete.out |
|---|---|
| 3 3 11111 4 1010101 0 10 | 2 2 3 |
Explicaţie
Sunt două numere mai mici sau egale decât 31 = 11111 cu gradul de frumuseţe 3: 15 = 1111 şi 30 = 11110.
Sunt două numere mai mici sau egale decât 85 = 1010101 cu gradul de frumuseţe 4: 31 = 11111 şi 62 = 111110.
Sunt trei numere mai mici sau egale decât 2 = 10 cu gradul de frumuseţe 0: 0 = 0, 1 = 1, 2 = 10.
