Fişierul intrare/ieşire:trei.in, trei.outSursă
AutorValentina PredaAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.1 secLimită de memorie5000 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Trei (clasa a 10-a)

Un număr natural nenul se numeste “treinumăr” dacă el se poate scrie ca sumă de puteri distincte ale lui trei. De exemplu, numărul 37 este treinumăr deoarece 37 = 27 + 9 + 1, iar numărul 18 nu este un treinumăr. Pentru un interval închis [a,b] să se determine câte treinumere aparţin intervalului. De exemplu intervalul [7, 27] conţine 5 treinumere: 9, 10, 12, 13 si 27.

Date de intrare

Din fişierul de intrare trei.in se citesc de pe prima linie două numere naturale N şi P şi de pe urmatoarele N linii câte două numere ce reprezintă capetele unui interval.

Date de ieşire

În fişierul de ieşire trei.out se va scrie pe prima linie câte dintre cele N intervale conţin cel puţin P treinumere.

Restricţii

  • 3 ≤ N ≤ 10 000
  • 3 ≤ P ≤ 10 000
  • 1 ≤ a[i] < b[i] ≤ 1 000 000, unde a[i] şi b[i] sunt capetele intervalelor, i=1,2,..N

Exemplu

trei.intrei.out
4 3
7 23
5 10
35 39
41 60
2

Explicaţie

Intervalul [7, 23] conţine treinumerele 9,10,12,13 ; intervalul [5, 10] conţine treinumerele 9 şi 10; intervalul [35, 39] conţine treinumerele 36, 37,39; intervalul [41, 60] nu conţine niciun treinumăr.

Trebuie sa te autentifici pentru a trimite solutii. Click aici