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, N segmente de lungime 1, paralalele cu axele de coordonate, in asa fel incat sa se poata ajunge din orice punct in orice alt punct al figurii, mergand doar pe segmentele trasate (fig. 1).

Dupa ce au stabilit tabla de joc, in modul descris mai sus, pot incepe sa coloreze, alternativ, segmentele. Jucatorul aflat la mutare, poate sa coloreze un segment doar daca este latura a unui patrat de 1×1 care nu are colorata nicio alta latura. Pierde cel ce nu mai poate efectua vreo colorare.

Spre exemplu (fig. 2), jucatorul aflat la mutare poate sa coloreze segmentele 1, 2, 3, si respectiv, 4. Nu poate colora, insa, segmentele 5 si 6 pentru ca zonele a si b nu reprezinta patrate de dimnesiune 1×1 si, in plus, in patratul c a fost colorata, anterior, o latura. De asemenea, nici segmentul 7 nu poate fi colorata deoarece, patratul d are, la randul lui, colorata o latura.

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 contine numarul natural N reprezentand numarul de segmente desenate. Urmeaza apoi N cvadruplete (x1,y1,x2,y2), reprezentand coordonatele unui segment.

Date de iesire

In fisierul de iesire jpg.out se va scrie, pe prima linie, 1 daca Dubluveu are strategie de castig, sau 2, altfel. Daca Presedintele castiga, pe a doua liniie se vor scrie toate posibilitatiile acestuia de a face prima mutare pentru a-l infrange pe Primul Ministru.

Restrictii

• 1 ≤ N ≤ 50
• fiecare segment are lungimea 1 si este paralel cu OX sau cu OY
• pentru 40% din teste N ≤ 13
• pentru 70% din teste N ≤ 25

Exemplu

Cum se trimit solutii?