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

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


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

Cei n deţinuţi ai unei închisori, numerotaţi de la 1 la n, trebuie să sape un şanţ dispus în linie dreaptă între două puncte A şi B, situate la distanţa de 250 km unul de celălalt, pe care există 251 borne kilometrice numerotate de la 0 la 250. Fiecare deţinut are însă o pretenţie, ″e doar democraţie, nu?″: el doreşte să sape doar undeva în zona dintre borna x şi borna y. Pe lângă aceste pretenţii închisoarea se confruntă şi cu o altă problemă: nu are suficienţi paznici angajaţi.

Cerinţă

Cunoscându-se numărul n de deţinuţi şi pretenţiile lor, să se determine locul/locurile unde vor fi puşi deţinuţii să sape într-o zi de muncă, respectându-se pretenţiile lor, astfel încât numărul de paznici necesari pentru a păzi cei n deţinuţi să fie minim. Intervalul în care poate păzi un paznic nu poate conţine două sau mai multe zone disjuncte dintre cele exprimate de deţinuţi în preferinţele lor.

Date de intrare

Fişierul de intrare sant1.in are pe prima linie numărul n de deţinuţi. Pe fiecare dintre următoarele n linii există câte două numere naturale, ai bi, separate printr-un spaţiu (ai≤bi), care reprezintă pretenţia deţinutului. Mai exact pe linia i+1 (1 ≤ i ≤ n) este descrisă pretenţia deţinutului cu numărul de ordine i.

Date de ieşire

Fişierul de ieşire sant1.out va conţine pe prima linie numărul natural k reprezentând numărul minim de paznici necesari pentru paza celor n deţinuţi scoşi la lucru. Pe următoarele 2k linii vor fi descrise locurile unde vor fi puşi să sape deţinuţii, astfel: fiecare pereche de linii (2j, 2j+1) va conţine pe linia 2j trei numere naturale p xj yj, separate prin câte un spaţiu reprezentând numărul de ordine al paznicului şi bornele kilometrice xj) şi yj unde va păzi paznicul p, iar pe linia 2j+1 vor fi scrise numerele de ordine ale deţinuţilor care sapă în această zonă, separate prin câte un spaţiu, ordonate crescător.

Restricţii

1 ≤ n ≤ 10000
0 ≤ ai ≤ bi ≤ 250
, pentru orice i, 1 ≤ i ≤ n
0 ≤ xj ≤ yj ≤ 250
, pentru orice j, 1 ≤ j ≤ k
Un deţinut poate să sape şi într-un singur punct (″în dreptul bornei kilometrice numerotată cu x″)
În cazul în care există mai multe soluţii se va afişa una singură
Numerele de ordine ale paznicilor vor fi scrise în fişier în ordine crescătoare
Numerotarea paznicilor începe de la 1

Exemple

sant1.insant1.outExplicaţii
3 0 20 8 13 30 60 2 1 8 13 1 2 2 30 60 3 sunt necesari 2 paznici: paznicul 1 va păzi între borna 8 şi borna 13, iar deţinuţii păziţi sunt 1 şi 2; paznicul 2 va păzi între borna 30 şi borna 60, iar deţinutul păzit este 3
4 10 20 2 5 30 40 5 7 3 1 10 20 1 2 5 5 2 4 3 30 40 3 sunt necesari 3 paznici: paznicul 1 va păzi între borna 10 şi borna 20, iar deţinutul păzit este 1; paznicul 2 va păzi la borna 5, iar deţinuţii păziţi sunt 2 şi 4; paznicul 3 va păzi între borna 30 şi borna 40, iar deţinutul păzit este 3
5 10 30 30 32 0 30 27 30 27 28 2 1 30 30 1 2 3 4 2 27 28 5 sunt necesari 2 paznici: paznicul 1 va păzi la borna 30, iar deţinuţii păziţi sunt 1, 2, 3 şi 4; paznicul 2 va păzi între borna 27 şi borna 28, iar deţinutul păzit este 5
!Soluţia nu este unică!

autor: Prof. Marinel Şerban
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2006: borg, diamant, matrice1, petrom, ratina, vitale, acolor, cifru1, evo, part, trasee, bombo, cub2, prieteni2, sg1, fact, limbaj, panouri, pereti, zumzi, adun, sport1, baschet1, mere3, roboti, tzigla, morse, powerpuff
De acelaşi autor: premii, finala, fractii, trei, manevre, nrcuv, an, vopsea, opmat, tramvai, bipal, kpal, sarpe, replace, factori, barca, perechi, grupe, cod, reactii, factura, decript, trenuri, holo, cifre, firma, tribile, mesaj, tricouri, pajura, monede, programs, fry, repeat, red, pavaj, bacan, nrbinar, invest, cutie2, loc, depou, nr3, zid, felinare, sir3, sqr, carte, labirint, stea, count, evaluare, super, schimb, zaruri, vectori, spirala, desen1, rima, ceas1, romane, sms, bac, excursia, joc7, furnici, munte1, cezar, marcare, excursie1, culmi, sume1, schi, nr4, fractie, cod3, medii, tren3, top, imagine, ocr, perfect, pluton, reforma, alee, ceas2, paritate, borcane, aranjare, comoara1, culmi1, reactivi, submult, sablon1, sir8, sume2, dansatori, smith, tom, matriosca, asociativ, control1, calorii, immortal, concat, mat, cubinvers, mine, divizori, cheie, stelar, joct, minmax, cladire, adunscad, razboi, ore, oras1, sumprod, prisme, operatii1, lgdrum, unupatru, chibrituri, extraprime, prieten, rebus1, grindina, opmult, betisoare, antitero, clase, pagini, ornament, ordine, spioni1
Despre Greedy: lac, sumdif, checkin, baby, startrek, placi, gramezi, mese, jobs, politics, joc3, playlist, carte, exam, subperm, piloti, barca1, pitici, bombe, pic, bac, pal, antena, culmi, numar2, lover, volei1, ab3, camion1, aranjare, popas, reactivi, mesaj2, dp, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, micro, triburi, testament, nor, eoliene, vintage, cifre5, agenda, monede2, charlie, scadere, barci
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre sortare: harta, index, sort, concurs, baby, patrate2, repeat, turist, bacan, toys, scor2, chimie2, politics, submat, scoici, ham, jokes, trecere, multiplu, paralel, tvshow, sirag1, tabara, munte, sport, puncte1, sume1, schi, granita, tren3, volei1, poze, maroco, dreptc, dist1, tir1, control, mosia, popas, reactivi, siruri1, coach, anag, matrice4, sume2, urgenta, basm, vot, balcon, joc14, cerc, k1, segm, calorii, ordonare, greutati, arctir, macheta, poligon4, centrala, robot4, lcdr, maxviz, sdmin, qtri, arme, flori1, parc1, mijloc, bile6, proiecte, patru, drept2, subsecvente, cursa1, eoliene, vintage, dreapta, riglef, rebus1, rascoala, zimeria, praslea, aperm, unudoi, gropi1, piscina, restaurare, cabana, culori3
surse trimise | ajutor