Fişierul intrare/ieşire:bcolor.in, bcolor.outSursăLot 2006
AutorEmilian MironAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Bcolor

Omida Smith s-a apucat din nou de colorat. De data aceasta s-a gandit sa incerce cu grafuri neorientate cu N noduri etichetate de la 1 la N si M muchii numerotate de la 1 la M.

La o plimbare, Smith porneste din nodul etichetat cu 1, se plimba pe muchiile grafului, dupa care se intoarce in nodul de plecare. Astfel, drumul parcurs de Smith incepe si se termina cu nodul 1, poate trece de mai multe prin acelasi nod si de asemenea poate trece de mai multe ori prin aceeasi muchie. Muchiile grafului sunt initial colorate in alb, iar la fiecare trecere a omizii peste o muchie aceasta isi schimba culoarea: din alba devine rosie si din rosie devine alba.

Fiecarui drum ii corespunde astfel o colorare finala a muchiilor, pe care vom numi configuratie posibila si o vom reprezenta ca un sir de M elemente reprezentand in ordine culorile finale ale muchiilor (A pentru alb, respectiv R pentru rosu). Omida a observat ca din toate configuratiile posibile, nu toate sunt frumoase. Exista unele muchii speciale care nu arata bine decat daca au o anumita culoare.

Smith vrea sa dea lovitura pe piata de grafuri de arta, asa ca genereaza pentru un graf dat toate configuratiile frumoase posibile in ordine lexicografica. Va lansa pe piata cea de a K-a configuratie generata, configuratiile fiind numerotate incepand cu 1.

Cerinta

Sa se determine cea de a K-a configuratie frumoasa posibila, in ordine lexicografica.

Date de intrare

Pe prima linie a fisierului de intrare bcolor.in se vor afla numerele naturale N, M, K separate prin cate un spatiu. Pe urmatoarele M linii se vor afla descrierile muchiilor grafului.

Pe linia i+1 se va afla descrierea muchiei i, formata din 3 numere naturale x, y, z separate prin cate un spatiu. Numerele x si y reprezinta nodurile care sunt extremitatile muchiei, iar z este un numar care poate lua valorile cu semnificatia de mai jos:

  • z=0     muchia nu este speciala
  • z=1     muchia este speciala, trebuie neaparat colorata in alb
  • z=2     muchia este speciala, trebuie neaparat colorata in rosu.

Date de iesire

Fisierul de iesire bcolor.out va contine o singura linie formata din M caractere din multimea {A, R} reprezentand in ordine culorile muchiilor din cea de a K-a configuratie frumoasa posibila pentru graful din fisierul de intrare.

Restrictii si precizari

  • 1 ≤ N, M ≤ 200
  • 1 ≤ K ≤ 108
  • Exista minim K configuratii frumoase posibile pentru graful dat.
  • Muchiile din fisierul de intrare sunt distincte.

Exemplu

bcolor.inbcolor.out
10 10 2
1 2 0
3 5 1
2 3 0
3 4 0
4 5 0
5 2 0
2 4 0
6 7 0
7 8 0
8 6 0
AAAARRRAAA

Explicatii

Configuratiile frumoase posibile in ordine lexicografica sunt:

  1. AAAAAAAAAA
  2. AAAARRRAAA
  3. AARRAARAAA
  4. AARRRRAAAA
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content