Šaha zirdziņa ceļojums

ID: zirgs2
Grūtība: 2/5
Laika limits: 1

Uzdevums

Ļoti, ļoti lielas rūtiņu lapas visas rūtiņas pēc kārtas sanumurētas tā, kā redzams 1. zīmējumā.

Kādā no laukuma rūtiņām novietots šaha zirdziņš. Katrā gājienā zirdziņš pēc šaha noteikumiem (2. zīmējumā pelēkā krāsā iekrāsotas visas tās rūtiņas, uz kurām zirdziņš drīkst izdarīt nākošo gājienu) pārvietojas uz to iepriekš neapmeklēto rūtiņu, kuras numurs ir mazākais iespējamais. Zirdziņš nevienā brīdī nedrīkst "nokāpt" no lapas. Piemēram, ja sākumā zirdziņš atrodas 6. rūtiņā, tad nākošajā gājienā zirdziņš pārvietosies uz 3. rūtiņu (jo pārējo trīs atļauto gājienu rūtiņās ierakstītie skaitļi ir lielāki - 9, 17 un 18).

1.zīm. Rūtiņu numerācija 2.zīm. Zirdziņa iespējamie gājieni

Uzrakstiet programmu, kas dotam zirdziņa sākotnējās rūtiņas numuram N un gājienu skaitam K nosaka, kāds būs tās rūtiņas numurs, kurā pēc K-tā gājiena izdarīšanas atradīsies zirdziņš!

 

Ievaddati

Teksta faila zirgs2.dat vienīgajā rindā dotas divu naturālu skaitļu N (1 ≤ N ≤ 100 000) un K (1 ≤ K ≤ 100 000) vērtības, kas atdalītas ar tukšumzīmi.

 

Izvaddati

Teksta faila zirgs2.rez vienīgajā rindā jāizvada naturāls skaitlis - tās rūtiņas numurs, kurā zirdziņš atradīsies pēc K-tā gājiena izdarīšanas. Ja, izdarot gājienus, kādā brīdī iestājas situācija, ka zirdziņš nevar izdarīt gājienu (visās atļautajās rūtiņās zirdziņš jau ir bijis iepriekš), tad failā jāizvada vārds "NEVAR", kam seko tās rūtiņas numurs, no kuras zirdziņš nevarēja izdarīt gājienu. Starp "NEVAR" un rūtiņas numuru jābūt tieši vienai tukšumzīmei.

 

Piemērs

zirgs2.datzirgs2.rez
5 1
7
  
zirgs2.datzirgs2.rez
1 4
13
  
zirgs2.datzirgs2.rez
13 13
16
  
zirgs2.datzirgs2.rez
100 4000
NEVAR 45

 

Atsauces

Uzdevums izmantots Latvijas 20. informātikas olimpiādes I (skolas) kārtā.
© 2001-2002 olimps! http://www.lio.lv/olimps/