triti2

Triti2

== include(page="template/taskheader" task_id="triti2") ==

Poveste şi cerinţă...

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$.
 
h2. 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.

h2. Date de intrare

Fişierul de intrare $triti2.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $triti2.out$ ...

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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ K ≤ 1 000$
* $1 ≤ N ≤ 10^1000^$
* 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^6^$
* Pentru alte $45%$ din teste $N ≤ 10^18^$

h2. Exemplu
table(example). |_. triti2.in |_. triti2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 7 13
| 2121010

|
h3. Explicaţie

...

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

== include(page="template/taskfooter" task_id="triti2") ==

5502