Nosaukums
Hex spēle (hex)
Laika limits
0.50s
Atmiņas limits
32.0 MB
Grūtība
77%

Definīcija

Hex ir abstrakta stratēģijas spēle ko patstāvīgi izgodroja vairāki cilvēki - 1942. gadā Piets Heins un 1948. gadā Džons Našs. Spēles laukumam ir romba forma un to veido 11x11 seštūra lauciņi. Spēli spēle divi spēlētāji un katrs vēlas savienot divas pretējās laukuma malas lai uzvarētu. Katrā gājienā spēlētājs aizpilda vienu brīvu lauciņu. Ļoti bieži spēles gaitā veidojas laukumiņu kopas, kas pēctam tiek savienotas savā starpā. Lai gan spēle izklausās vienkārša, tā atļauj dažādas stratēģijas kas liek lauzīt galvu ne veinam vien Gudrinieku ciema iedzīvotājam. 

Draugiem Group un Printful darbinieki ir labi draugi un bieži spēlē Hex. Lai nokļūtu no Printful biroja Ojāra Vācieša ielā uz Draugiem Group biroja Krasta ielā ir jāšķerso Daugava. Abi uzņēmumi ir izlēmuši būvet tiltu pār Daugavu, lai padārītu pārvietošanos ērtāku. Tilta projektēšana uz būvniecība tika uzticēta Hex spēlētājiem.... Viņi Daugavu sadalīja Hex laukumā un izlēma, ka visoptimālākais tilta projektēšanas veids ir balstīts uz Hex spēles notiekumiem. Līdzīgi, kā Hex spēlē, arī tilta būvētāji katrā gājienā var aizpildīt vienu lauciņu. Abas puses ir izpildījušas vienādu gājienu skaitu. Kā redzams attēlā, tilta projektētāji ir aizrāvušies ar spēles stratēģiju (sarkanie laukumi ir pašreizējais tilts no Daugavas labā krasta un zilie lauciņi ir jau uzbēvētais tilts no kreisā krasta). Palīdzi atrast mazāko lauciņu skaitu, kas vēl jāaizpilda (zaļā līnija ir viens no variantiem), lai savienotu jau izveidotos tilta fragmentus. 

Katrā Daugavas krastā uzbūvētā tilta daļa sastāv no savstarpēji savienotiem lauciņiem. Katrā krastā ir tikai viena tilta daļa.


Ievaddatu raksturojums

Pirmajā rindā dots Hex lauciņa malas garums n (10<=n<=100) un izdarīto gājienu skaits k (1<=k<=100). Otrajā rindā dots aizpildīto lauciņu skaits Daugavas labajā krastā m (1<=m<=100). Sekojošās m rindas satur aizpildīto lauciņu koordinātas x,y (x = kolonas numurs, y - rindas numurs). 

Nākamajā rindā dots aizpildīto lauciņu skaits Daugavas kreisajā krastā h (1<=h<=100). Sekojošās h rindas satur aizpildīto lauciņu koordinātas x,y (x = kolonas numurs, y - rindas numurs). 

 


Izvaddatu raksturojums

Izvadīt mazāko lauciņu skaitu, kurus aizpildot ir iespējams savienot abus tilta fragmentus.


Paraugdati

Stdin
11 8
8
5 1
5 2
5 3
4 3
6 2
6 1
4 1
3 3
8
6 11
6 10
7 11
7 9
8 10
5 11
7 8
7 10
Stdout
6

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.