Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | jpg.in, jpg.out | Sursă | Winter Challenge 2008, Runda 2 |
| Autor | Bogdan Alexandru Stoica | Adăugată de |  Bogdan-Alexandru Stoica •fireatmyself |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Joc pe grid
Devenind Presedintele Romaniei, Dubluveu a trebuit sa renunte la jocurile de noroc, dar pentru ca ii place foarte mult sa se joace si-a gasit repede o noua distractie. In timpul liber, cand nu sunt prinsi cu treburile tarii, el si Primul Ministru joaca urmatorul joc. Deseneaza, pe o foaie de hartie, un carioaj (grid) de N*$N$ patratele. Sterg apoi niste muchii astfel incat, dupa aceasta operatie, sa se poata ajunge din orice segment la orice alt segment al gridului (fig. 1).
Dupa ce au stabilit tabla de joc, in modul descris mai sus, pot incepe sa stearga, alternativ, muchii. Jucatorul aflat la mutare, poate sa stearga o muchie daca si numai daca cel putin unul din cele doua patratele de care apartine nu are nicio muchie stearsa
Spre exemplu ($fig. 2$), jucatorul aflat la mutare vrea sa stearga muchia albastra. Ea apartine patratului rosu si patratului verde. Patratul rosu mai are doar 3 laturi desenate, dar patratul verde le are pe toate 4 si, deci, muchia poate fi stearsa. In fig. 3 muchia albastra nu poate fi stearsa, deoarece un patratele mai au 3 si, respectiv, 2 muchii nesterse. In cazul unui singur patrat "izolat" (fig. 4), toate cele 4 muchii apartin, evident, doar acelui patrat.
Cerinta
Stiind ca ambii jucatori joaca optim si ca Dubluveu incepe, intotdeauna, jocul, se cere sa determinati daca el are strategie de castig si, in caz, afirmativ sa-i indicati si prima mutare pe care trebuie sa o faca pentru a-l infrange pe Primul Ministru.
Date de intrare
Fisierul de intrare jpg.in ...
Date de iesire
In fisierul de iesire jpg.out ...
Restrictii
- ... ≤ ... ≤ ...
Exemplu
| jpg.in | jpg.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
