Jpg

Joc pe grid

== include(page="template/taskheader" task_id="jpg") ==

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. Formeaza apoi o figura, stergand unele din segmentele carioajului, astfel incat, sa se poata ajunge din orice segment la orice alt segment al gridului (fig. 1).

Devenind Presedintele Romaniei, Dubluveu a trebuit sa renunte la jocurile de noroc, dar 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 u$ (o unitate), 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$}).

!problema/jpg?f1.jpg!

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, care se intersecteaza dupa acea muchie, nu are nicio latura stearsa+
 
!problema/jpg?f2.jpg!
 
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.

Dupa ce au stabilit tabla de joc, cei doi pot incepe sa coloreze, alternativ, segmentele. Jucatorul aflat la mutare, poate sa coloreze un segment doar daca acesta este +latura a unui patrat de 1x1 care nu are colorata nicio alta latura+. Spre exemplu ({$fig. 2$}), jucatorul aflat la mutare poate sa coloreze oricare din segmentele marcate cu **verde**. Nu poate colora, insa, niciun segment marcat cu **albastru** pentru ca zona **a** este un patrat de latura $2 u$ (doua unitati), iar zona **b** (care este patrat de 1x1) are deja colorata o latura (cea cu rosu). De asemenea, nici cel marcat cu **mov** nu poate fi colorat deoarece, patratul **c** (singurul de care apartine segmentul) are, la randul lui, o latura colorata anterior.
Pierde cel ce nu mai poate efectua nicio colorare.

h2. 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.

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 toate posibilitatile de a face prima mutare pentru a-l infrange pe Primul Ministru.

h2. Date de intrare

Fisierul de intrare $jpg.in$ ...

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.

h2. Date de iesire

In fisierul de iesire $jpg.out$ ...

In fisierul de iesire $jpg.out$ se va scrie, pe prima linie, $1$ daca Dubluveu are strategie de castig, sau 2, altfel. Daca Dubluveu castiga, pe a doua liniie se vor scrie toate posibilitatiile acestuia de a face prima mutare pentru a-l infrange pe Primul Ministru. Mai exact, vor fi afisati in ordine crescatoare indicii segmentelor cu proprietatea ca daca segmentul respectiv este primul pe care Dubluveu il coloreaza, atunci Dubluveu va castiga jocul.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 50$
* fiecare segment are lungimea $1$ si este paralel cu $OX$ sau cu $OY$
* coordonatele sunt numere naturale cuprinse in intervalul $[0,50]$
* Toate segmentele din fisierul de intrare sunt distincte
* pentru $30%$ din teste $N ≤ 13$
* pentru $60%$ din teste $N ≤ 23$

h2. Exemplu
table(example). |_. jpg.in |_. jpg.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicatie
 
...

| 8
2 1 2 0
1 2 2 2
2 2 2 1
0 2 1 2
1 1 2 1
2 0 1 0
1 1 0 1
1 1 1 2
| 1
2 3 5 8 |
| 9
1 2 1 3
1 2 2 2
1 3 2 3
2 1 2 2
3 1 2 1
2 3 2 2
3 1 3 2
3 2 3 3
3 2 2 2
| 2
|

== include(page="template/taskfooter" task_id="jpg") ==

2751