.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » arbgraf

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
 .campion
arbgraf


Timp maxim de execuţie/test:
0.7 secunde
Memorie totală disponibilă/stivă:
64MB/8 MB

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.

Exemplu

arbgraf.in arbgraf.out
3 1
1 3 2 4 0 5 6
4 3 4
5 9
6 8
2 7
1 6
prof. Marius Nicoli
Colegiul Naţional „Fraţii Buzeşti” Craiova
mariusnicoli@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2010: greiere, divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, stelar, atelier, secv9, ny, radical, select, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, fluviu, camera616, aritm, stele, covor, subm, mess, secvnumber, cladire, ssmax, parcela, pion, subs, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
De acelaşi autor: secvente1, raze, bile5, 235, dreptunghiuri, triunghi2, albine1, puteri35, miere, left, reuniune, cazare, atletism, fluviu, stele, zar1, poteci, avioane, obstacole, liste, acoperire1, minusk, efect, b2k, progresii, reconst, mijloc, romb, alune, patru, galbeni, schi1, restaurare, sort2dist
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, maxq, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, sediu, string, tv, izo, zoo, ratina, vitale, camion1, arbfind, cezar1, tcast, dep, curent, spp, frunze, sea2, culori, color, urgenta, nori, treegame, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
surse trimise | ajutor