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 câte 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
Fişierul de intrare wildcards.in ...
Date de ieşire
În fişierul de ieşire wildcards.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| wildcards.in | wildcards.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
