Fişierul intrare/ieşire:	triti2.in, triti2.out	Sursă	Tiberiu Popoviciu 2011, Clasele 11-12
Autor	Cosmin-Mihai Tutunaru	Adăugată de	Cosmin-Mihai Tutunaru •stocarul
Timp execuţie pe test	0.05 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/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 ≤ 10¹⁰⁰⁰
• 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 ≤ 10⁶
• Pentru alte 45% din teste N ≤ 10¹⁸

Exemplu

Explicaţie

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

Cum se trimit solutii?