z-first-grade

U slucaju da niste znali, mali Z se rodio i odrastao u Magicnoj Zemlji. Njegov prvi posao je bio da pravi Magicni Kanap bilo koje duzine. U njegovoj radionici ima neogranicene zalihe kanapa duzine 1 Inc. On takodje ima dve masine koje mogu raditi sledece:

- Prva masina radi samo tokom dana, i za dati kanap duzine L (1 <= L <= N), moze da produzi kanap K puta, sve dok je duzina novo-dobijenog kanapa u intervalu [1, N].

- Druga masina radi samo tokom noci, i od dva kanapa duzina L1 i L2 u intervalu [1, N] moze da napravi kanap duzine L1 + L2 i L1 - L2, sve dok je duzina novo-dobijenog kanapa u intervalu [1, N].

Druga masina je stara, pa kada proizvodi kanap, kanap postane veoma vruc, pa se masina ne moze koristiti za dalju proizvodnju tokom te noci.

Za dato K i N, pravljenje kanapa neke duzine zahteva odredjen broj dana. Na primer, za K = 2 i N = 11, da bi se napravio kanap duzine 11 malom Z-u treba tri dana. Pocinje sa tri kanapa duzine 1 Inc. Prvog dana, produzava prvi kanap jednom (sa ciniocem 2), i produzava drugi kanap dva puta (oba puta ciniocem 2). Dakle pre prve noci ima kanape duzine 1,4 i 8. Sad prve noci pravi kanap duzine 3 (od kanapa sa duzinama 4 i 1), drugog dana ne treba da radi nista. Napokon, druge noci napravi kanap duzine 11 (sto je 8 + 3).

Hajdemo sada da pazljivo posmatramo slucaj kada je K = 3 i N = 10. Prvog dana, mali Z moze da napravi sledece kanape:
- Duzine 1
- Duzine 3 = 1 * 3
- Duzine 9 = 1 * 3 * 3
Sad, posle prve noci (ovo je vec dan drugi!) moce da napravi sledece kanape:
- Duzine 2 = 1 + 1 ili 3 - 1
- Duzine 4 = 3 + 1
- Duzine 6 = 9 - 3
- Duzine 8 = 9 - 1
Tokom drugog dana moze da dobije novu duzinu tako sto ce da produzi neki kanap K puta. Napokon, posle druge noci (ovo je treci dan kada moze da ima sledece kanape)
- Duzine 5 = 3 + 2
- Duzine 7 = 6 + 1