| Fișierul intrare/ieșire | trei.in, trei.out | Sursă | |
|---|---|---|---|
| Autor | Valentina Preda | Adăugată de |
Victor Manz
•
vmanz
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 5000 KB |
| Scorul tău | N/A | Dificultate |
  1
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
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.in | trei.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.
