Fişierul intrare/ieşire:wildcards.in, wildcards.outSursăLot Deva Seniori 2019, baraj 2
AutorAdrian Budau, Andrei Popa, Mihai CalanceaAdăugată deCoroian_DavidCoroian David Coroian_David
Timp execuţie pe test0.25 secLimită de memorie512000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Wildcards

Numim pattern un şir nevid format doar din caracterele 0, 1 şi ?. Spunem că două patternuri A şi B de aceeaşi lungime se potrivesc dacă şi numai dacă caracterele ? pot fi înlocuite convenabil cu 0 şi 1 astfel încât cele două şiruri să devină identice. De exemplu, pentru A = “110?1”, B = “1?001”, C = “??1?1”, şirurile A şi B se potrivesc (se poate forma şirul “11001” prin înlocuirea semnelor de întrebare cu valori),
dar şirurile A şi C nu se potrivesc.

Se dă un arbore (graf neorientat conex aciclic) cu N noduri. Se cere să se atribuie fiecărui nod câte un şir format din caracterele 0, 1 şi ? (un pattern) astfel încât să se respecte următoarele proprietăţi:

  • Toate patternurile să aibă aceeaşi lungime, care să fie cât mai mică (a se vedea rubrica Punctare).
  • Pentru oricare două noduri distincte u şi v, patternurile asociate acestora se potrivesc dacă şi numai dacă există muchia (u, v) în arbore.

Date de intrare

Fişierul de intrare wildcards.in va conţine pe prima linie numărul de noduri din arbore N. Pe următoarele N - 1 linii fişierul va conţine câte două numere a şi b cu semnificaţia că există o muchie între a şi b.

Date de ieşire

Fişierul de ieşire wildcards.out va contine N linii, pe linia i aflandu-se patternul nodului i.

Punctaj

În concurs punctajul pe un subtask era minimul dintre scorurile obţinute la testele din subtaskul respectiv, dar datorită unor limitări tehnice, punctarea se va face in felul următor:

SubtaskPunctajConstrangeri
1
6 puncte
2 ≤ N ≤ 100, praginf = 100, pragsup = 100
2
9 puncte
2 ≤ N ≤ 10, praginf = 100, pragsup = 100
3
5 puncte
2 ≤ N ≤ 10000, praginf = 34, pragsup = 34, arborele este un lant de N noduri
4
5 puncte
2 ≤ N ≤ 10000, praginf = 34, pragsup = 34, arborele este binar complet
5
35 puncte
2 ≤ N ≤ 10, praginf = 101, pragsup = 200
6
40 puncte
2 ≤ N ≤ 10, praginf = 34, pragsup = 42

Exemplu

wildcards.inwildcards.out
4
1 2
1 3
1 4
???
000
0?1
11?
3
1 2
2 3
0
?
1
5
1 2
1 3
3 4
3 5
?00
000
1??
110
101
2
2 1
?
?

Explicaţie

Aceasta este figura pentru primul, respectiv cel de-al treilea exemplu:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?