Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | judete.in, judete.out | Sursă | .campion 2005 |
| Autor | Dan-Ionut Fechete | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Judete
In tara maimutelor exista N orase numerotate de la 1 la N. Orasele sunt conectate prin sosele, astfel incat exista un drum unic intre oricare 2 orase din tara. Nefiind in stare sa administreze toate orasele presedintele hotaraste urmatoarele:
- tara va fi impartita intr-un numar de judete, astfel incat fiecare oras sa apartina exact unui judet
- drumul dintre oricare 2 orase din acelasi judet nu trece prin orase din alt judet
- numarul minim de orase dintr-un judet este K
Fie T maximul dintre numarul de orase apartinand aceluiasi judet.
Cerinta
Scrieti un program care sa gaseasca o impartire in judete cu T minim pentru o configuratie de orase si sosele date.
Date de intrare
Pe prima linie a fisierului de intrare judete.in sunt scrise cele doua numere naturale N K separate printr-un singur spatiu. Pe urmatoarele N-1 linii sunt scrise cate doua numere naturale cuprinse intre 1 si N, separate prin spatiu, reprezentand doua orase intre care exista o sosea.
Date de iesire
Prima linie a fisierului judete.out va contine T minim pentru configuratia din fisierul de intrare.
Restrictii
- 3 ≤ K ≤ N ≤ 127
- pe soselele din tara maimutelor se circula in ambele sensuri.
Exemplu
| judete.in | judete.out |
|---|---|
| 10 3 1 2 2 3 3 4 3 5 2 6 6 7 6 8 8 9 1 10 | 4 |
Explicatie
O impartire posibila a oraselor in judete este
1, 2, 10
3, 4, 5
6, 7, 8, 9
Fiecare oras apartine exact unui singur judet.
Fiecare judet contine cel putin 3 orase.
Numarul maxim de orase dintr-un judet este 4 (si acesta este minim posibil).
