Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-08-04 14:39:35.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:cezar.in, cezar.outSursăOJI 2007, clasele 11-12
AutorRodica PinteaAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.1 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cezar

In Roma antica exista N asezari senatoriale distincte, cate una pentru fiecare dintre cei N senatori ai Republicii. Asezarile senatoriale sunt numerotate de la 1 la N, intre oricare doua asezari existand legaturi directe sau indirecte. O legatura este directa daca ea nu mai trece prin alte asezari senatoriale intermediare. Edilii au pavat unele dintre legaturile directe dintre doua asezari (numind o astfel de legatura pavata "strada"), astfel incat intre oricare doua asezari senatoriale sa existe o singura succesiune de strazi prin care se poate ajunge de la o asezare senatoriala la cealalta.
Toti senatorii trebuie sa participe la sedintele Senatului. In acest scop, ei se deplaseaza cu lectica. Orice senator care se deplaseaza pe o strada plateste 1 ban pentru ca a fost transportat cu lectica pe acea strada.
La alegerea sa ca prim consul, Cezar a promis ca va dota Roma cu o lectica gratuita care sa circule pe un numar de K strazi ale Romei astfel incat orice senator care va circula pe strazile respective, sa poata folosi lectica gratuita fara a plati. Strazile pe care se deplaseaza lectica gratuita trebuie sa fie legate intre ele (zborul, metroul sau teleportarea nefiind posibile la acea vreme).
In plus, Cezar a promis sa stabileasca sediul salii de sedinte a Senatului intr-una dintre asezarile senatoriale aflate pe traseul lecticii gratuite. Problema este de a alege cele K strazi si amplasarea sediului salii de sedinte a Senatului astfel incat, prin folosirea transportului gratuit, senatorii, in drumul lor spre sala de sedinte, sa faca economii cat mai insemnate. In calculul costului total de transport, pentru toti senatorii, Cezar a considerat ca fiecare senator va calatori exact o data de la asezarea sa pana la sala de sedinte a Senatului.

Cerinta

Scrieti un program care determina costul minim care se poate obtine prin alegerea adecvata a celor K strazi pe care va circula lectica gratuita si a locului de amplasare a salii de sedinta a Senatului.

Date de intrare

Fisierul cezar.in contine
# pe prima linie doua valori N K separate printr-un spatiu reprezentand numarul total de senatori si numarul de strazi pe care circula lectica gratuita
# pe urmatorele N-1 linii se afla cate doua valori i j separate printr-un spatiu, reprezentand numerele de ordine a doua asezari senatoriale intre care exista strada.

Date de iesire

...

Restrictii

  • ... ≤ ... ≤ ...

Exemplu

cezar.incezar.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicatie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?