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

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


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
16MB / 1MB

Ţara lui Arbore-Vodă este reprezentată ca un arbore cu N noduri (numerotate de la 1 la N), unde fiecare nod reprezintă un punct de întâlnire a mai multor străzi bidirecţionale. Una dintre caracteristicile acestei ţări este faptul că străzile sunt paralele cu axele de coordonate. Mai mult, un punct de întâlnire (un nod) poate avea cel mult 4 străzi incidente astfel: cel mult o stradă incidentă spre stânga, una spre dreapta (ambele orizontale), una care merge în sus şi una care merge în jos (ambele verticale).
Deoarece şoferii turişti pierd prea mult timp când trebuie să schimbe direcţia într-o intersecţie (punct de întâlnire a străzilor), ei îşi calculează, în funcţie de timpul pe care-l au la dispoziţie, numărul maxim K de schimbări de direcţie pe care le vor face.
Astfel, ei îşi pun problema să găsească cel mai lung traseu pe care l-ar putea parcurge cu maşina făcând maxim K schimbări de direcţie şi fără să treacă de două ori prin aceeaşi intersecţie (prin acelaşi nod). Lungimea unui traseu este egală cu numărul de străzi care aparţin acelui traseu. Spunem că şoferul schimbă direcţia dacă după ce a efectuat o deplasare de-a lungul axei Ox efectuează o deplasare de-a lungul axei Oy sau viceversa.

Cerinţă

Dându-se K, să se determine lungimea celui mai lung traseu în care se fac maxim K schimbări de direcţie, precum şi câte astfel de trasee de lungime maximă există. Două trasee diferă dacă există cel puţin o stradă într-un traseu care să nu se regăsească în celălalt.

Date de intrare

Fişierul de intrare masina.in va conţine pe prima linie cele două numere naturale N şi K. Următoa¬rele N linii descriu arborele. Linia i+1 conţine 4 numere naturale l d r u separate prin spaţiu, reprezentând numerele de ordine ale intersecţiilor adiacente cu intersecţia i: l reprezintă numărul de ordine al intersecţiei în care se ajunge urmând strada care pleacă din i şi merge spre stânga (spunem că l este vecinul la stânga al lui i), d reprezintă vecinul de jos al lui i, r vecinul la dreapta şi u vecinul de sus. Dacă vecinul la stânga lipseşte, l va fi egal cu 0 (similar pentru d, r şi u).

Date de ieşire

Fişierul de ieşire masina.out va conţine o singură linie pe care se vor găsi două numere naturale separate printr-un singur spaţiu, reprezentând lungimea celui mai lung drum, respectiv numărul drumurilor ce satisfac condiţia din enunţ şi au lungime maximă.

Restricţii

1 ≤ N ≤ 10 000
0 ≤ K < N

Două intersecţii se pot găsi în aceeaşi locaţie, însă ele rămân diferite (ca în arborele: N = 5 şi nodurile 1 - 0, 0, 2, 0; 2 – 1, 3, 0, 0; 3 – 4, 0, 0, 2; 4 – 0, 0, 3, 5; 5 – 0, 4, 0, 0 unde 1 şi 5 ocupă aceeaşi locaţie însă sunt noduri diferite).
Pentru 50% din teste K<=100.

Exemple

masina.inmasina.out
12 4 0 2 3 4 0 0 0 1 1 0 0 0 5 1 0 0 6 0 4 0 0 7 5 0 8 0 9 6 10 11 7 12 7 0 0 0 0 0 8 0 0 0 0 8 0 8 0 0 7 4

autor: Iolanda Popa
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor