Fişierul intrare/ieşire:triti2.in, triti2.outSursăTiberiu Popoviciu 2011, Clasele 11-12
AutorCosmin-Mihai TutunaruAdăugată destocarulCosmin-Mihai Tutunaru stocarul
Timp execuţie pe test0.1 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Triti2

Triţii sunt numere formate din cifrele 0, 1 şi 2 cu proprietatea că diferenţa în modul a oricăror două cifre vecine (pe poziţii consecutive) este exact 1.

Cerinţă

Foarte curios din fire, Ţirbi vrea să afle care este al N-lea trit cu exact K cifre. Cum el este pasionat de Silverlight şi nu de algoritmică, vă roagă pe voi să îl ajutaţi.

Date de intrare

Fişierul de intrare triti2.in conţine pe prima linie numerele naturale K şi N separate printr-un singur spatiu.

Date de ieşire

Fişierul de ieşire triti2.out conţine al N-lea trit cu exact K cifre dacă acesta există, sau "-1" (fără ghilimele) dacă nu există cel puţin N triţi distincţi cu exact K cifre.

Restricţii

  • 1 ≤ K ≤ 1 000
  • 1 ≤ N ≤ 101000
  • Deoarece triţii sunt numere, nu pot avea prima cifră 0.
  • Numerotarea triţilor începe de la 1.
  • Al N-lea trit este cel mai mic trit ce are exact N-1 triţi mai mici decât el.
  • Triţii se compară la fel ca şi numerele.
  • Pentru 25% din teste N ≤ 106
  • Pentru alte 45% din teste N ≤ 1018

Exemplu

triti2.intriti2.out
7 13
2121010

Explicaţie

1010101
1010121
1012101
1012121
1210101
1210121
1212101
1212121
2101010
2101012
2101210
2101212
2121010

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content