| Fişierul intrare/ieşire: | ludo.in, ludo.out | Sursă | Shumen 2019 Juniori |
| Autor | Iliyan Yordanov | Adăugată de |  Matteo Verzotti •Matteoalexandru |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ludo
A aparut in magazine o noua versiune a binecunoscutului joc "Nu te supara frate", numit "Ludo". Deni si Bob se decid imediat sa il cumpere si incep sa invete regulile: Se da o harta de joc care are casute numerotate de la 1 la N. Anumite casute sunt vecine. Avem un pion care poate fi plasat intr-o casuta si care poate fi mutat dintr-alta vecina.
Harta este speciala - pornind de la o casuta, pionul nu poate reveni in ea fara sa treaca prin casute vizitate anterior. Primul jucator alege o casuta in care plaseaza pionul. Apoi este randul celui de-al doilea jucator sa mute si acestia incep sa mute alternativ pionul dintr-o casuta in alta vecina. O casuta vizitata anterior devine marcata si nu mai poate fi folosita. Jucatorul care nu mai poate muta pionul intr-o casuta vecina nemarcata pierde si celalalt castiga. Deni si Bob sunt experimentati in astfel de jocuri, drept pentru care vor juca mereu optim. Deni incepe. Ea stie cum sa aleaga o casuta de inceput astfel incat sa fie castigatoare.
Scrieti un program care sa citeasca parametrii jocului si sa afiseze pentru fiecare casuta daca reprezinta o pozitie de inceput castigatoare sau pierzatoare.
Date de intrare
Fişierul de intrare ludo.in contine pe prima linie numerele N si M - numarul de casute ale hartii de joc si numarul de perechi de casute vecine. De pe fiecare dintre urmatoarele M linii se citesc doi intregi, x si y, reprezentand indicii a doua casute invecinate.
Date de ieşire
În fişierul de ieşire ludo.out se va afisa o secventa de 0 si 1, fara spatii, unde 0 inseamna ca pozitia este una de inceput pierzatoare si 1, ca este una de inceput castigatoare.
Restricţii
- 1 ≤ N ≤ 5 * 105
- 1 ≤ M ≤ 5 * 105
- Pentru 10 puncte, 1 ≤ N, M ≤ 104 si casutele formeaza o linie dreapta.
- Pentru 30 de puncte, 1 ≤ N, M ≤ 3 * 103
- Pentru 15 puncte, 1 ≤ N, M ≤ 2 * 105, N = 2s - 1 pentru un anume s si 2s-1 casute au un singur vecin, o casuta are doi vecini si celelalte au cate trei vecini.
- Pentru 35 de puncte, 1 ≤ N, M ≤ 2 * 105
- Pentru 10 puncte, 1 ≤ N, M ≤ 5 * 105
Exemplu
| ludo.in | ludo.out |
|---|---|
| 5 4 1 2 1 3 2 4 2 5 | 00011 |
Explicaţie
Pentru un mod de joc optim, iesirea reprezinta ca Deni pierde daca plaseaza la inceput pionul intr-una din casutele marcate cu 1, 2 sau 3, iar daca il plaseaza in oricare dintre celelalte, castiga. Daca Deni plaseaza pionul in casuta cu numarul 1, Bob poate muta pionul in casuta cu numarul 3, iar Deni nu va mai avea mutari disponibile deoarece casuta 1 este deja marcata. Analog, Deni va pierde daca plaseaza pionul in casuta cu numarul 2. Pentru casutele 4 si 5, ea are o strategie de castig.
