Fişierul intrare/ieşire:bazaconii.in, bazaconii.outSursăAlgoritmiada 2009, Runda 2
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bazaconii

Andrei si Maria sunt doi copii care se tin mereu de bazaconii. Ultima bazaconie facuta de cei doi a fost sa piarda o foaie pe care era scris un sir de N numere naturale. Ei nu isi mai amintesc acum ce numere erau in sir, dar isi amintesc in schimb M relatii de forma i j k cu semnificatia ca suma xor a numerelor din sir aflate pe pozitiile i si j este k. Copiii au incercat sa reconstituie sirul initial pe baza acestor relatii, dar nu au reusit si de aceea va cer voua ajutorul. Ei isi mai doresc ca in cazul in care exista mai multe siruri de numere care satisfac toate relatiile sa stie doar sirul cel mai mic din punct de vedere lexicografic.

Date de intrare

Fişierul de intrare bazaconii.in contine pe prima linie numarul T, reprezentand numarul de teste ce urmeaza a fi descrise. In continuare urmeaza cele T teste, pe prima linie aflandu-se N si M, separate de un singur spatiu, avand semnificatia din enunt. Urmeaza apoi M linii, pe fiecare aflandu-se trei numere naturale separate de un singur spatiu, i, j si k, avand semnificatia din enunt.

Date de ieşire

În fişierul de ieşire bazaconii.out se vor afisa T linii, pe linia i aflandu-se raspunsul pentru al i-lea test din fisierul de intrare. Daca nu exista niciun sir care sa respecte conditiile se va afisa doar numarul -1, altfel se vor afisa N numere naturale separate de un singur spatiu, reprezentand cel mai mic sir din punct de vedere lexicografic care respecta toate conditiile.

Restricţii

  • Pentru 20% din teste N ≤ 7 si se garanteaza ca solutia optima va avea toate valorile mai mici sau egale decat 20
  • 1 ≤ T ≤ 10
  • 1 ≤ N, M ≤ 10 000
  • Pentru fiecare triplet i j k, 1 ≤ i, j ≤ N si 0 ≤ k ≤ 2 000 000 000
  • Pentru a obtine suma xor a doua numere naturale se scriu numerele in reprezentare binara, apoi fiecare bit al rezultatului va fi 1 numai daca bitii corespunzatori ai celor doua numere sunt diferiti, altfel va fi 0. Exemplu: 0 xor 1 = 1, 1 xor 0 = 1, 1001 xor 1100 = 0101. In C/C++ exista operatorul "^" care face aceasta operatie, iar in pascal exista operatorul "xor".
  • Un sir X este mai mic din punct de vedere lexicografic decat un sir Y daca exista un k astfel incat Xi=Yi pentru orice i<k si Xk<Yk

Exemplu

bazaconii.inbazaconii.out
2
2 2
1 2 3
1 2 1
2 1
1 2 1
-1
0 1

Explicaţie

Pentru al doilea test o solutie posibila era si 1 0, dar sirul 0 1 este cel mai mic din punct de vedere lexicografic.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content