Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2019-05-22 09:40:22.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	wildcards.in, wildcards.out	Sursă	Lot Deva Seniori 2019, baraj 2
Autor	Adrian Budau, Andrei Popa, Mihai Calancea	Adăugată de	Coroian David •Coroian_David
Timp execuţie pe test	0.125 sec	Limită de memorie	512000 kbytes
Scorul tău	N/A	Dificultate	N/A

Wildcards

Numim pattern un sir nevid format doar din caracterele 0, 1 si ?. Spunem că două patternuri A si B de aceeasi lungime se potrivesc daca si numai daca caracterele ? pot fi ı̂nlocuite convenabil cu 0 si 1 astfel incat cele două siruri să devină identice. De exemplu, pentru A = “110?1”, B = “1?001”, C = “??1?1”, sirurile A si B se potrivesc (se poate forma sirul “11001” prin inlocuirea semnelor de intrebare cu valori),
dar sirurile A si C nu se potrivesc.

Se da un arbore (graf neorientat conex aciclic) cu N noduri. Se cere să se atribuie fiecărui nod cate un sir format din caracterele 0, 1 si ? (un pattern) astfel incat să se respecte următoarele proprietati:

* Toate patternurile sa aiba aceeasi lungime, care să fie cat mai mica (a se vedea rubrica Punctare).
* Pentru oricare două noduri distincte u si v, patternurile asociate acestora se potrivesc dacă si numai dacă există muchia (u, v) ı̂n arbore.

Date de intrare

Fisierul de intrare wildcards.in va contine pe prima linie numarul de noduri din arbore N. Pe urmatoarele N - 1 linii fisierul va contine cate doua numere a si b cu semnificatia ca exista o muchie intre a si b

Date de ieşire

Fisierul de iesire wildcards.out va contine N linii, pe linia i aflandu-se patternul nodului i.

Punctaj

Subtask	Punctaj	Constrangeri
1	6 puncte	2 ≤ N ≤ 100, prag_inf = 100, prag_sup = 100
2	9 puncte	2 ≤ N ≤ 10, prag_inf = 100, prag_sup = 100
3	5 puncte	2 ≤ N ≤ 10000, prag_inf = 34, prag_sup = 34, arborele este un lant de `N` noduri
4	6 puncte	2 ≤ N ≤ 10000, prag_inf = 34, prag_sup = 34, arborele este binar complet
5	42 puncte	2 ≤ N ≤ 10, prag_inf = 101, prag_sup = 200
6	32 puncte	2 ≤ N ≤ 10, prag_inf = 34, prag_sup = 42