Fişierul intrare/ieşire:23.in, 23.outSursăIIOT 2019-20 Runda 1
AutorAlexandru PetrescuAdăugată deunibucPoli2019Comisia IIOT 2019-20 unibucPoli2019
Timp execuţie pe test0.6 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

23

Bugland are o populaţie mixtă, având ca populaţie atât gândaci cu 2 antene cât şi gândaci cu 3 antene.
În mod evident, gândacii cu 2 antene numără în baza 2 (de altfel ei zic că sunt 10 tipuri de gândaci în Bugland), şi cei cu 3 antene numără în baza 3.

Un număr este considerat nepotrivit dacă cele două specii de gândaci îl privesc ca având suma cifrelor diferită. Altfel spus, un număr este nepotrivit dacă suma cifrelor din scrierea lui în baza 2 şi în baza 3 diferă.
Pentru a promova egalitatea gândacilor, numerele nepotrivite sunt stric interzise.

Avand în vedere că gândacii nu ştiu să numere decât de la 1 până la N, câte numere permise există?

Date de intrare

Din 23.in se va citi de pe prima linie numărul T de scenarii.
Următoarele T linii conţin câte un numar N, cel mai mare număr pe care gândacii îl ştiu. De observat că gândacii ştiu numai numere naturale.

Date de ieşire

În 23.out se vor afişa T numere pe o singură linie, separate prin spaţiu, al i-lea număr fiind răspunsul la al i-lea scenariu.

Restricţii

  • 1 \leq T \leq 1000
  • 1 \leq N_i \leq 10^7
  • Pentru teste in valoare de 20 de puncte, 1 \leq \displaystyle{\sum_{i=0}^{T} N_i} \leq 10^6
  • Pentru alte teste in valoare de 30 de puncte, 1 \leq N_i \leq 10^6

Exemplu

23.in23.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 în baza 2, respectiv 3 astfel:

baza 10baza2baza 3suma în baza 2suma în baza 3
11111
210212
3111021
41001112
51011223
61102022
71112133
810002214
9100110021
10101010122

Astfel, numerele permise sunt 1, 6, 7, 10.

Numerele permise sunt 1, 6, 7, 10.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?