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

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


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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 doua orase din tara. Nefiind in stare sa administreze toate orasele presedintele hotaraste urmatoarele:

  1. tara va fi impartita intr-un numar de judete, astfel incat fiecare oras sa apartina exact unui judet
  2. drumul dintre oricare doua orase din acelasi judet nu trece prin orase din alt judet
  3. 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

  • 2 < N, K < 128
  • Pe soselele din tara maimutelor se circula in ambele sensuri.

Exemplu

judete.in judete.out Explicatie

10 3
1 2
2 3
3 4
3 5
2 6
6 7
6 8
8 9
1 10

4

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).

Fechete Dan Ionut
Universitatea Bucuresti
Facultatea de Matematica si Informatica
mailto:f_dany@eminem.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: 2sec, croco, tetris2, trafic, monede1, mesaj1, diamant, ratina, import, drept1, gard, pitici1, curent
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor