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

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


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

Asa cum probabil ati ghicit, este vorba despre o pasune obisnuita, cu o multime de flori împrastiate pe suprafata ei.
Albinutele industriale zboara printre flori, aterizeaza pe flori si culeg polen pentru a produce mierea. Întrucât viata si prosperitatea întregii comunitati depinde de aceasta, fiecare floare trebuie sa fie vizitata, pentru a aduna cât mai mult polen posibil.
Maya este albinuta care planifica modul în care albinutele industriale viziteaza toate florile. O planificare consta dintr-o succesiune de multimi de flori (de pozitii de flori, mai exact). Fiecare albinuta primeste o multime de flori si trebuie sa viziteze toate florile din multimea respectiva, într-o ordine arbitrara. Orice floare poate fi vizitata o data sau de mai multe ori.
O albinuta care primeste o multime de flori trebuie sa îsi planifice zborul, alegând o ordine de vizitare a florilor care sa aiba cost minim si vizitând apoi florile în aceasta ordine. Pentru o ordine de vizitare a florilor data, definim costul ca fiind distanta maxima dintre doua flori vizitate consecutiv. Deci costul unei multimi de flori este costul obtinut atunci cand albina viziteaza florile in ordinea de cost minim. Costul unei planificari este costul maxim al tuturor multimilor din planificare.

Cerinta

Scrieti un program care sa o ajute pe Maya sa determine o planificare de cost minim.

Date de intrare

Fisierul de intrare pasune.in contine pe prima linie doua numere naturale separate prin spatiu F B (F reprezinta numarul de flori, iar B reprezinta numarul de albine care culeg polen). Fiecare dintre urmatoarele F linii contine câte doua numere naturale separate prin spatiu X Y (pe linia i+1, X este abscisa, iar Y este ordonata celei de a i-a flori).

Date de iesire
Fisierul de iesire pasune.out contine o singura linie pe care se afla costul minim al unei planificari, rotunjit la doua zecimale.

Restrictii
1 <= F <= 2000
1 <= B <= F
1 <= X, Y <= 10000

Eroarea admisa este de 0.01 (cu alte cuvinte diferenta dintre rezultatul corect si rezultatul din fisierul de iesire nu trebuie sa depaseasca 0.01).

Exemple

pasune.in pasune.out pasune.in pasune.out pasune.in pasune.out
3 2
1 1
2 3
3 2
1.41 5 3
1 1
1 4
1 5
5 1
5 5
3.00 7 4
1 1
3 9
9 4
2 2
6 4
5 5
6 9
3.00

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:ema at mail.dntis.ro

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2004: cifre1, super, apm, bile1, factk, schimb, caini, secvreg, descfib, maraton, masina1, otilia, multiplu, tub, remi, m01, robot1, na, sir23, paralel, zaruri, bomboane, dotnet, divizor, tren1, joc5, tvshow, pachete, soldati1, echipe, omizi, suma1, aedaro, concurs1, windows, comb, renju, latime, vectori, ghici, subperm, puncte, mere1, spirala, distanta, piloti
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
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, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, 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
Software recomandat
surse trimise | ajutor