Numim arbgraf de ordin N un graf neorientat care se
obţine astfel:
- se pleacă de la un arbore binar in care numărul de muchii de
la rădăcină până la oricare frunză este N-1;
- nodurile arborelui sunt noduri ale grafului, iar graful nu are şi
alte noduri;
- orice muchie între un nod şi fii săi în arbore este muchie în arbgraf;
- între oricare 2 noduri vecine de pe acelaşi nivel al arborelui există
muchie în graf, graful nu mai are şi alte muchii;
- nodurile de pe ultimul nivel sunt frunze;
- nodurile de pe celelalte nivele au 1 sau 2 fii.
În exemplul următor este desenat un arbgraf de ordin 3.
Într-un arbgraf păstrăm proprietatea de etajare pe niveluri a nodurilor
moştenită de la arborii cu rădăcină (graful fiind neorientat, parcurgerea
muchiilor se poate face însă în ambele sensuri). Astfel, nodurile ce
nu au descendenţi le numim frunze. Iniţial, frunzele sunt doar pe ultimul
nivel.
O omidă pleacă din cel mai din stânga nod al ultimului nivel şi doreşte
să elimine K noduri de pe ultimul nivel, cele mai din stânga K, începând
cu nodul de plecare. Ea are grijă însă să nu lase frunze pe nivelurile
superioare, aşa că dacă prin eliminarea unor noduri vor apărea frunze
pe nivelurile superioare, le va elimina şi pe acestea. Odată terminată
acţiunea, omida ajunge pe al K+1 – lea nod de pe ultimul nivel (care
acum este cel mai din stânga de pe acel nivel), cu forţe proaspete.
Ea doreşte acum ca mergând doar pe muchii ale grafului rămas, să ajungă
în nodul din vârf trecând exact o dată prin fiecare nod rămas (muchiile
incidente nodurilor eliminate au fost şi ele eliminate). Doreşte însă
să facă acest traseu cu efort minim. Înainte de plecare, ea trebuie
să eticheteze nodurile grafului cu secvenţe distincte formate din cifre
zecimale. Două secvenţe sunt distincte daca au lungime diferită sau
există o poziţie pentru care caracterele din cele 2 secvenţe sunt diferite.
Efortul de trecere între 2 noduri legate prin muchie va fie egal cu
“distanţa” dintre secvenţele asociate etichetelor nodurilor între care
se trece.
Distanţa între 2 etichete se defineşte astfel (considerăm poziţiile
numerotate din stânga):
- dacă cele 2 etichete au aceeaşi lungime, distanţa e dată de numărul
de poziţii în care diferă cifrele
- dacă au lungimi diferite, se adaugă la valoarea anterioară diferenţa
lungimilor lor.
Exemple: distanţa între 00 şi 0 este 1; distanţa între 0203 si 120 este
2
Cerinţă
Date fiind N şi K cu semnificaţia din enunţ precum şi configuraţia grafului,
determinaţi: M – numărul de noduri rămase în urma eliminării celor K frunze
de pe ultimul nivel, E – efortul minim cu care omida poate realiza traseul
dorit şi o etichetare a nodurilor pentru care se poate realiza un traseu
cu efort minim. Dacă sunt mai multe posibilităţi de etichetare se cere
une dintre cele în care suma lungimilor etichetelor asociate nodurilor
este minimă.
Date de intrare
Fişierul arbgraf.in are pe prima linie în ordine N şi K, 2 numere naturale separate printr-un spaţiu, cu semnificaţia din
enunţ. Pe linia a doua sunt 2N-1 numere naturale consecutive începând
cu 1. De asemenea, poate apărea şi valoarea 0 de 0, 1 sau mai multe
ori. Numerele sunt separate prin câte un spaţiu şi au următoarea semnificaţie.
Pe poziţia 1 se găseşte rădăcina. În general, pe poziţiile 2•i şi 2•i+1 se găsesc fii nodului de pe poziţia i, vecinul stâng, respectiv drept.
Prezenţa valorii 0 semnifică lipsa acelui fiu.
Date de ieşire
Fişierul arbgraf.out are următoarea structură:
Pe prima linie 3 numere naturale separate prin cate un spaţiu: M (numărul de
noduri rămase după eliminarea celor K frunze), E (efortul minim cu care
omida poate realiza traseul dorit) şi L suma lungimilor etichetelor.
Pe următoarele M linii câte 2 elemente separate printr-un spaţiu: codul
unui nod respectiv eticheta sa. Nodurile apar în ordinea parcurgerii drumului
de la start la final.
Restricţii
2 <= N <= 20
0 < K < numărul de frunze;
Pentru afişarea corectă a primei valori se acordă
20% din punctaj.
Pentru afişarea corectă a primelor 2 valori se acordă 30% din punctaj.
Pentru afişarea corectă a primelor 3 valori se acordă 40% din punctaj.
