ŠIOM — Žaidimas su šaške

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1999_3e1_zaid_saske_jau.in

Rezultatų failas: lmio_1999_3e1_zaid_saske_jau.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Žaidimas su šaške

Žaidimą su šaške žaidžia vienas žmogus. Lentoje vienas šalia kito nupiešta $n$ kvadratėlių. Jie sunumeruoti nuo 1 iki $n$ . Į kiekvieną kvadratėlį įrašytas sveikasis skaičius nuo $-n$ iki $n$ . Pirmame kvadratėlyje įrašytas nulis. Jame žaidimo pradžioje pastatoma šaškė.

Žaidimas pradedamas metant lošimo kauliuką, turintį nuo 1 iki 6 akių. Žaidėjas pastumia šaškę per tiek kvadratėlių į priekį, kiek iškrito kauliuko akių. Jei šaškė sustoja ant kvadratėlio su teigiamu skaičiumi – ji per tiek kvadratėlių pastumiama į priekį, jei ant neigiamo – per tiek kvadratėlių perstumiama atgal. Taip vaikštoma tol, kol patenkama ant kvadratėlio su nuliu. Tada vėl metamas kauliukas ir judama į priekį.

Jei iš paskutiniojo kvadratėlio šaškei dar reikia judėti į priekį, ji patenka į pirmąjį kvadratėlį. Jei judėdama atgal šaškė patenka į pirmąjį langelį, tai iš ten niekur toliau nebeina – sustoja ir vėl metamas kauliukas.

Sutarta, kad perstumiant šaškę iš vieno kvadratėlio į kitą, ji aplanko ne tik tuos du, bet ir visus jos kelyje pasitaikančius kvadratėlius. Šaškės perstūmimas nuo vieno kvadratėlio ant kito gretimo laikomas žingsniu. Vadinasi, vienu ėjimu šaškė gali padaryti kelis žingsnius.

Žaidimas baigiamas, kai aplankomi visi kvadratėliai.

Panagrinėkime pavyzdį. Piešinyje parodyta, kaip judės šaškė, jei mėtant kauliuką iškrito 1, 2, 1. Kiekvienas žingsnis pavaizduotas rodykle. Iki žaidimo pabaigos šaškė padarė 15 žingsnių.

Pavyzdys

Užduotis

Parašykite algoritmą, randantį tokią kauliuko akių seką, kuriai iškritus žaidimas baigtųsi per mažiausią žingsnių skaičių.

Pradiniai duomenys

Pirmoje eilutėje nurodytas kvadratėlių skaičius $n$ . Likusiose $n$ eilučių įrašyta po vieną natūralųjį skaičių, nuo $-n$ iki $n$ . Tai kvadratėlių viduje esantys skaičiai.

Rezultatai

Rezultatus – kauliuko akių seką – spausdinkite po vieną skaičių eilutėje.

Pavyzdžiai

Pradiniai duomenys	Rezultatai	Paaiškinimas
7 0 -3 2 6 0 -2 1	4 2	Šaškė iš viso padarys šešis žingsnius

Ribojimai