Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | 23.in, 23.out | Sursă | IIOT 2019-20 Runda 1 |
| Autor | Alexandru Petrescu | Adăugată de |  Comisia IIOT 2019-20 •unibucPoli2019 |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
23
Bugland are o populatie mixta, avand ca populatie atat gandaci cu 2 antene cat si gandaci cu 3 antene.
In mod evident, gandacii cu 2 antene numara in baza 2 (de altfel ei zic ca sunt 10 tipuri de gandaci in Bugland), si cei cu 3 antene numara in baza 3.
Un numar este considerat nepotrivit daca cele doua specii de gandaci il privesc ca avand suma cifrelor diferita. Altfel spus, un numar este nepotrivit daca suma cifrelor din scrierea lui in baza 2 si in baza 3 difera.
In mod evident, pentru a promova egalitatea gandacilor, numerele nepotrivite sunt interzise.
Avand in vedere ca gandacii nu stiu sa numere decat de la 1 pana la N, cate numere permise exista?
Date de intrare
Fişierul de intrare 23.in contine T, numarul de scenarii.
Urmatoarele T linii contin cate un numar N, cel mai mare numar pe care gandacii il stiu.
De observat ca gandacii stiu numai numere naturale.
Date de ieşire
În fişierul de ieşire 23.out va contine T linii, pe a i-a linie fiind raspunsul la al i-lea scenariu.
Restricţii
- 1 ≤ T ≤ 1000
- 1 ≤ N i ≤ 107
- Pentru teste in valoare de 20 de puncte, 1 ≤ suma din N i ≤ 106
- Pentru alte teste in valoare de 30 de puncte, 1 ≤ N i ≤ 106
Exemplu
| 23.in | 23.out |
|---|---|
| 10 1 2 3 4 5 6 7 8 9 10 | 1 1 1 1 1 2 3 3 3 4 |
Explicaţie
Numerele de la 1 la 10 sunt scrise in baza 2, respectiv 3 astfel:
- 1, 1
- 10, 2
- 11, 10
- 100, 11
- 101, 12
- 110, 20
- 111, 21
- 1000, 22
- 1001, 100
- 1010, 101
Numerele permise sunt 1, 6, 7, 10.
