TA�KAI

UˇDUOTIS
Tai stalo žaidimas dviems. Lentoje yra N langelių, sunumeruotų nuo 1 iki N. Tarp langelių nupieštos vienos krypties rodyklės. Žaidėjas gali perstumti šaškę iš vieno langelio į kitą tik tada, jei yra nupiešta rodyklė, vedanti iš pirmojo langelio į antrą. Kiekviename langelyje įrašyta po teigiamą skaičių (vertę). Visos vertės skirtingos. Kiekvienas langelis būtinai priklauso vienam iš žaidėjų, kurį vadinsime šio langelio šeimininku. Pirmasis langelis yra startinis. Pradžioje abu žaidėjai turi po 0 taškų.

Lentos langelių skaičius, rodyklių išsidėstymas, langelių vertės ir jų šeimininkai yra fiksuojami prieš pradedant žaidimą ir žaidimo metu nesikeičia. 

Žaidžiama šitaip. Langelį, kuriame stovi šaškė, pažymėkime C. ˇaidimo prad˛ioje C yra startinis langelis. Žaidimo ėjimą sudaro šios operacijos:
1.	Jeigu langelio C vertė yra didesnė už šio langelio šeimininko turimą taškų sumą, tai šeimininko taškai tampa lygūs C. Kitu atveju �io langelio �eimininko ta�kai lieka tie patys. Abiem atvejais kito žaidėjo taškai nekeičiami.
2.	Po to langelio C šeimininkas pasirenka rodyklę (išeinančią iš C) ir perkelia šaškę į �ios rodyklės rodomą langelį. Atkreipkite dėmesį, kad tas pats žaidėjas gali padaryti keletą ėjimų iš eilės.

Žaidimas baigiamas, kai šaškė sugrįžta į startinį langelį. Laimi tas, kuris baigus žaidimą turi daugiausiai taškų.

Rodyklės visuomet nupieštos taip, kad: 
-	Iš langelio, kuriame yra šaškė, visuomet galima išeiti (t.y. iš jo išeina rodyklė); 
-	Bet kurį langelį P galima pasiekti i� startinio langelio (t.y. egzistuoja iš rodyklių sudarytas kelias vedantis į P); 
-	Žaidimas būtinai pasibaigs po baigtinio ėjimų skaičiaus. 

Parašykite programą, kuri žaistų šį žaidimą ir laimėtų. Testuojant pradinės žaidimo situacijos bus tokios, kad bus įmanoma laimėti nepriklausomai nuo to, kas pradeda. Priešininkas būtinai žais optimaliai.

PRADINIAI DUOMENYS IR REZULTATAI
Jūsų programa turi skaityti iš standartinio įvesties įrenginio (standard input) ir rašyti į standartinį išvesties įrenginį (standard output). Jūsų programa bus pirmasis žaidėjas,  o priešininkas – antrasis žaidėjas. Atkreipkite dėmesį, kad žaidimą pradeda pirmojo langelio �eimininkas, o ne būtinai pirmasis žaidėjas. Pirmiausia jūsų programa turi perskaityti žemiau aprašytus pradinius duomenis iš standartinio įvesties įrenginio.

Pirmoje eiluteje yra vienas sveikasis skaicius N, 1N1000, rei�kiantis langeliu skaiciu. Kiekvienoje tolesniu N eiluciu ira�yta po N sveikuju skaiciu, nusakanciu rodykles. Jei i� langelio i i langeli j nukreipta rodykle, tai i–osios eilutes j–asis skaicius lygus 1. Prie�ingu atveju �is skaicius lygus 0.

Tolesneje eiluteje yra N skaiciu, nusakanciu langeliu �eimininkus. Jei langelio i �eimininkas yra pirmasis ˛aidejas (jus), tuomet i–asis �ios eilutes skaicius lygus 1, prie�ingu atveju lygus 2.

Tolesneje eiluteje vel ira�yta N sveikuju skaiciu. Tai langeliu vertes. Jei i–ojo langelio verte yra j, tuomet i–asis �ios eilutes skaicius lygus j. Visu langeliu vertes yra skirtingos ir joms galioja: 1jN.

Perskaičius pradinę situaciją prasideda žaidimas. Šaškė yra pirmame langelyje. Jūsų programa turi žaisti žemiau aprašytu būdu ir baigti žaidimą, kai šaškė sugrįžta į pirmą langelį:

•	Jei jums reikia atlikti ejima, tuomet jusu programa i standartini i�vesties irengini turi i�vesti tolesnio langelio numeri P, 1 PN. 
•	Jei ejima reikia atlikti jusu prie�ininkui, tuomet jusu programa turi perskaityti i� standartinio ivesties irenginio langelio numeri P, 1PN.

Panagrinėkime tokį pavyzdį. Žaidimą apibūdina 1 paveikslas. Pirmojo žaidėjo langeliai pažymėti apskritimais, antrojo – kvadratėliais. Kvadratėlyje arba apskritime įrašyta langelio vertė, o pats langelio numeris užrašytas šalia apskritimo (ar kvadratėlio).

1 paveikslas

Įvedimas		išvedimas	paaiškinimas

4	  				N
0 1 0 0  				Informacija apie rodykles, išeinančias i� pirmo langelio
0 0 1 1				Informacija apie rodykles , išeinančias iš antro langelio
0 0 0 1				Informacija apie rodykles , išeinančias iš trečio langelio
1 0 0 0  				Informacija apie rodykles, išeinančias iš ketvirto langelio
1 1 2 2            			Langelių �eimininkai
1 3 4 2 				Langelių vertės
			2		Paeina 1 žaidėjas.
			4		Paeina 1 žaidėjas.
1					2 žaidėjas paeina į startinį langelį – žaidimas baigiamas.

Žaidimui pasibaigus, pirmasis žaidėjas turi 3 taškus, antrasis – 2 taškus. Laimi pirmasis žaidėjas.

NURODYMAI KAIP PROGRAMUOTI

Žemiau pateiktame pavyzdyje langelį saugo sveikojo tipo kintamasis target.

Jei programuojate Paskalio kalba, tai skaityti iš standartinio įvesties įrenginio ir rašyti į standartinį išvesties įrenginį turite tokiu būdu:

Readln(target);
Writeln(target);

PRIEMONĖS

Jums duota programa (score2 Linux’ui, score2.exe Windows’ams), kuri perskaitys žaidimo pradinę situaciją iš pradinių duomenų bylos score.in. Byloje esančių duomenų (pradinės žaidimo situacijos) formatas turi būti toks, kaip aprašyta aukščiau.
Pradinę situaciją programa įrašys į standartinį išvedimo įrenginį. Tuos rezultatus galėsite naudoti savo programos testavimui. Po to duotoji programa žais pagal atsitiktinę strategiją. Ji skaitys jūsų programos ėjimus iš standartinio įvesties įrenginio ir rašys savo ėjimus į standartinį išvesties įrenginį.

VERTINIMAS

Jei žaidimą laimėsite, už testą gausite visus taškus, jei pralaimėsite – 0 tašų. Testuojant jūsų programa bus leidžiama du kartus. Pirmą kartą jūsų programa žais su kita programa ir leidžiamas vykdymo laikas bus viena sekunde ilgesnis nei nurodyta sąlygoje. Vykdymo metu bus įsiminti pradiniai duomenys (t.y. pradinė žaidimo situacija ir visi antrojo žaidėjo ėjimai) bei jūsų išspausdinti ėjimai. Kai jūsų programa bus leidžiama antrą kartą, jai skirti duomenys jau bus nukreipiami iš bylos ir tuomet bus skaičiuojamas tikras jūsų programos vykdymo laikas. Beje, jūsų programa, vykdoma antrą kartą turėtų pateikti tuos pačius rezultatus kaip ir vykdant ją pirmąjį kartą.