Fişierul intrare/ieşire: | hex.in, hex.out | Sursă | ad-hoc |
Autor | Catalin Francu | Adăugată de | |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 4096 kbytes |
Scorul tău | N/A | Dificultate |
Hex
Jocul Hex se joacă pe o tablă de formă romboidală formată din hexagoane, cu latura de N hexagoane (tradiţional N = 11). Un jucător are piese roşii, celălalt albastre. Roşul mută primul. Pe rând, jucătorii plasează câte o piesă într-un hexagon. Roşul câştigă dacă face un lanţ neîntrerupt de piese care leagă latura stângă de cea dreaptă, iar albastrul câştigă dacă face un lanţ neîntrerupt de piese care leagă latura de sus de cea de jos. În exemplul alăturat, ordinea mutărilor a fost A - B - C - D - E - F. La mutarea F, albastrul a câştigat.
Se dau numărul N şi N2 mutări distincte şi corecte. Să se spună după a câta mutare jocul se încheie cu victorie. Se poate demonstra că nu există remize la Hex. (În practică, după mutarea câştigătoare partida se încheie, dar pentru problema de faţă toate cele N2 hexagoane vor fi ocupate).
Date de intrare
Fişierul de intrare hex.in conţine pe prima linie numărul N. Pe următoarele N2 linii se găseşte câte o mutare sub forma L C. Liniile şi coloanele sunt numerotate de la 1 la N. Liniile sunt orizontale, iar coloanele oblice de la stânga-sus spre dreapta jos.
Date de ieşire
În fişierul de ieşire hex.out se va tipări un singur număr: numărul primei mutări la care unul dintre jucători închide un lanţ câştigător.
Restricţii
- 1 ≤ N ≤ 500
Exemplu
hex.in | hex.out |
---|---|
3 2 1 2 2 1 2 1 3 2 3 3 2 1 1 3 3 3 1 | 6 |
Explicaţie
Vezi imaginea de mai sus.