Fişierul intrare/ieşire:trigame.in, trigame.outSursăStelele Informaticii 2007-2008, Clasele 11-12
AutorLiviu CiorteaAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Trigame

Fat-Frumos trebuie sa o salveze pe Ileana Cosanzeana din palatul Zmeului cel Rau. Totusi, Ileana nu vrea sa fie salvata, asa ca se decid sa joace un joc. Daca va castiga, Ileana ramane la Zmeu, altfel va pleca cu Fat-Frumos.

Palatul Zmeului are N camere, unele perechi de camere fiind unite prin coridoare, astfel incat din orice camera se poate ajunge in orice alta camera intr-un mod unic. Initial, luminile sunt aprinse in toate camerele. Cei doi incep jocul in camere diferite, si vor muta alternativ -- acest lucru este posibil, intrucat atat Ileana cat si Fat-Frumos au telefoane mobile. Intr-o mutare, fiecare personaj stinge lumina in camera curenta in care se afla, alege o camera vecina libera in care lumina este aprinsa si se deplaseaza in aceasta. Atat Ileana Cosanzeana cat si Fat-Frumos joaca optim: daca unul dintre ei are o strategie astfel incat sa fie sigur de victorie indiferent de mutarile adversarului, o va urma. Ileana va face prima mutare. Va pierde cel care nu va mai putea efectua nici o mutare, adica lumina este stinsa in toate camerele adiacente camerei in care se afla. Cu alte cuvinte, castigatorul este cel care muta ultimul.

Pentru ca autorul povestii nu mai stie care sunt camerele in care incep celor doua personaje, va trebui sa determinati, luand in considerare toate pozitiile initiale posibile, cate jocuri va castiga Ileana Cosanzeana.

Date de intrare

Fisierul de intrare trigame.in contine pe prima linie valoarea lui N. Urmatoarele N-1 linii vor contine cate doua numere naturale diferite a b, cu valori intre 1 si N, cu semnificatia ca exista un coridor intre camerele a si b.

Date de iesire

In fisierul de iesire trigame.out se va scrie un singur numar, reprezentand numarul de jocuri pe care le va castiga Ileana Cosanzeana.

Restrictii

  • 2 ≤ N ≤ 2048
  • Pentru 40% din datele de test, 2 ≤ N ≤ 64
  • Pentru alte 20% din datele de test, 2 ≤ N ≤ 256

Exemplu

trigame.intrigame.out
5
1 2
2 3
2 4
1 5
12

Explicatie

Din cele 20 de jocuri posibile, Ileana va castiga 12 jocuri, cele in care pozitiile initiale sunt: (1, 3) (1, 4) (1, 5) (2, 3) (2, 4) (2, 5) (3, 1) (3, 4) (3, 5) (4, 1) (4, 3) (4, 5) -- primul numar din pereche este pozitia Ileanei, al doilea este pozitia lui Fat-Frumos. De exemplu, pentru (3, 5), Ileana se va deplasa in camera 2, Fat-Frumos in camera 1, ultima mutare fiind a Ileanei care va muta in camera 4, castigand jocul.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content