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 |
Vezi solutiile trimise | Statistici
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 ≤ 10 prag_inf = 100 prag_sup = 100 |
Exemplu
| wildcards.in | wildcards.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
