Diferente pentru problema/acolor intre reviziile #24 si #40

Nu exista diferente intre titluri.

Diferente intre continut:

==Include(page="template/taskheader" task_id="acolor")==
==Include(page="template/raw")==
 
Omida-agent Smith s-a saturat sa tot distruga arborii si acum isi dezvolta simtul artistic - ii place mult mai mult sa-i coloreze.
 
De fiecare data cand vrea sa creeze o noua arbo-pictura isi ia cu el cele $K$ creioane colorate, isi alege un arbore din gradina si porneste la lucru.
 
Arborele ales de Smith este alcatuit din $N$ noduri, are ca radacina nodul $R$ si o forma potrivita pentru pictura:
* fiecare nod are cel mult doua crengi care duc spre doua noduri: unul la stanga si/sau unul la dreapta;
 
* intre oricare doua noduri exista un drum unic format din crengi distincte, pe care omida se poate plimba pentru a ajunge de la un nod la celalalt;
 
* nodurile din subarborele stang al unui nod sunt toate plasate mai la stanga decat acesta, iar cele din subarborele drept sunt toate mai la dreapta, de aceea nodurile au fost etichetate de la $1$ la $N$ de la cel mai din stanga pana la cel mai din dreapta.
Omida a observat ca picturile sale sunt frumoase doar daca respecta unele reguli de baza pe care le-a citit intr-o carte:
* orice nod trebuie sa fie colorat cu exact una dintre cele $K$ culori;
 
* un nod trebuie sa fie colorat diferit fata de parintele dinspre radacina (adica fata de nodul care preceda nodul respectiv atunci cand omida se plimba pe drumul de la radacina la nod);
 
* privit din exterior arborele trebuie sa fie colorat diferit de la stanga la dreapta: orice nod are o culoare diferita de cel mai apropiat nod la stanga de el si fata de cel mai apropiat nod la dreapta (cu alte cuvinte culoarea nodului etichetat cu $i$ trebuie sa fie diferita de culoarea nodurilor etichetate cu $i-1$, $i+1$).
h2. Cerinta
h2. Date de Intrare
Fisierul de intrare $acolor.in$ va contine pe prima linie numerele intregi $N, R, K$ separate prin cate un spatiu. Pe urmatoarele $N$ linii este descrisa structura arborelui. Mai exact, pe linia $i+1$ vor exista doua numere $st ~i~, dr ~i~$ separate printr-un spatiu, reprezentand nodul fiu spre stanga si respectiv nodul fiu spre dreapta al nodului $i$. Daca un nod nu are fiu spre stanga si/sau fiu spre dreapta atunci numarul corespunzator va fi $0$.
Fisierul de intrare $acolor.in$ va contine pe prima linie numerele intregi $N, R, K$ separate prin cate un spatiu. Pe urmatoarele $N$ linii este descrisa structura arborelui. Mai exact, pe linia $i+1$ vor exista doua numere $st{~i~}, dr{~i~}$ separate printr-un spatiu, reprezentand nodul fiu spre stanga si respectiv nodul fiu spre dreapta al nodului $i$. Daca un nod nu are fiu spre stanga si/sau fiu spre dreapta atunci numarul corespunzator va fi $0$.
h2. Date de Iesire
h2. Restrictii si precizari
* $0 < N &le; 100 000, 1 &le; R &le; N, 1 &le; K &le; 100$
* $In 40% din teste sunt indeplinite relatiile N &le; 100 si K &le; 10$
* $In 60% din teste sunt indeplinite relatiile N &le; 400 si K &le; 150$
* In $40%$ din teste sunt indeplinite relatiile $N &le; 100$ si $K &le; 10$
* In $60%$ din teste sunt indeplinite relatiile $N &le; 400 si K &le; 15$
h2. Exemplu
h2. Exemple
table(example). |_. acolor.in |_. acolor.out |_. figura  |
| 9 5 4
0 0
8 0
| 3601
| !http://www.infoarena.ro/task/acolor?action=download&file=arbore.gif! |
| !problema/acolor?image001.gif! |
| 3 1 2
0 3
0 0
2 0
| 0
|{color:red}.|
 
| &nbsp; |
==Include(page="template/taskfooter" task_id="acolor")==
 
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
1057