Fişierul intrare/ieşire:frumusete.in, frumusete.outSursăONIS 2014, Runda 1
AutorTeodor PlopAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.85 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.infrumusete.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content