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

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


Timp maxim de execuţie/test:
0.6 secunde
Memorie totala disponibilă/stivă:
2 MB/1 MB

Norii se formează atunci când vaporii invizibili de apă din aer (particule elementare al căror diametru este mai mic de 0.01mm)  se condensează în picături de apă vizibile sau în cristale de gheaţă.  Un nor conţine n particule elementare numerotate de la 1, 2, …, n.
Un proces important în formarea formaţiunilor noroase este procesul de coliziune şi captare în care coliziunea dintre particule elementare care se ridică şi coboară produce cuplarea (captarea) acestora în picături din ce în ce mai mari, care în final sunt destul de grele pentru a cădea pe pământ sub formă de ploaie. Numărul minim de particule elementare conţinute de o picătură ca să cadă pe pământ este de 3 particule.
Ca procesul de captare să aibă loc trebuie ca între două particule aflate în picături diferite să existe coliziune, picătura cu număr de particule mai mare atrage picătura cu număr de particule mai mic sau cel mult egal.
Pentru a se forma un nor Cumulonimbus (Cumulus - grămadă), adică un nor care aduce ploaia, sunt necesare cel puţin n/2+1 particule elementare distribuite în picături suficient de mari pentru a cădea pe pământ.

Cerinţă

Fiind date n, numărul de particule elementare, m, numărul de coliziuri şi cele m coliziuni, să se scrie un program ce determină numărul minim de picături necesare pentru formarea unui nor Cumulonimbus.

Date de intrare

Fişierul de intrare nor.in conţine pe prima linie două numere naturale separate prin spaţiu n şi m, n reprezentând numărul total de particule elementare, respectiv m numărul de coliziuni care se produc. Pe fiecare dintre următoarele m linii se află câte două numere naturale x şi y, 1≤x,y≤n, separate printr-un spaţiu, cu semnificaţia "particula x intră în coliziune cu particula y".

Date de ieşire


Fişierul de ieşire nor.out va conţine pe prima linie un număr natural k, reprezentând numărul minim de picături necesare pentru formarea unui nor Cumulonimbus. Pe cea de a doua linie vor fi scrise k numere naturale aflate în ordine descrescătoare, separate prin câte un spaţiu, ce reprezintă pentru fiecare picătură care cade din nor, numărul de particule elementare ce o alcătuiesc. Fiind un an secetos se va alege soluţia cu număr maxim de picături elementare.

Restricţii

  • 0 < n <= 15000
  • 0 < m <= 60000
  • Numărul maxim de particule elementare aflate într-o picătură este mai mic de 256.

Exemple

nor.in nor.out Explicaţie
11 7
1 2
1 11
4 5
5 9
4 7
4 9
3 10
2
4 3
Picăturile formate: (1,2,11), (4,5,7,9), (3,10)
Iar cele care pot să cadă pe pământ sunt formate din 4 respectiv 3 picături elementare

 

nor.in nor.out Explicaţie
14 12
1 2
1 3
1 4
1 5
1 6
7 8
8 9
9 10
7 11
12 13
12 14
13 14
2
6 5
Picăturile formate:
(1,2,3,4,5,6), (7,8,9,10,11), (12,13,14)
Se observă că o soluţie posibilă este formată din 6+3 picături elementare, dar se va alege soluţia cu 6+5 pentru că are număr mai mare de picături elementare

 

nor.in nor.out Explicaţie
30 7
5 7
2 3
10 14
14 6
9 15
7 30
3 2
0
Picăturile formate: (2,3), (5,7,30), (6,10,14), (9,15)
Nu sunt suficiente pentru a forma un nor Cumulonimbus

Ştiaţi că un nor Cumulonimbus poate atinge o înălţime de 18 km, dublul Everestului şi poate conţine peste o jumătate de milion de tone de apă!

prof. Eugen Nodea
Colegiul Naţional "Tudor Vladimirescu" Tg. Jiu
e_nodea@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2011: ore, pegals, valet, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ksecv, ripstick, antic, oak, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, sdmin, lista, operatii1, codarb, codpatrat, adprod, puncte4, qtri, reconst, gsm, subsiruri, mijloc, trifoi, cubulete, romb, maxbin, albine2, probleme, triburi1, megascoala, 2ndesc
De acelaşi autor: expresie1, tsunami, antic, compresie, gheizere, poly, unific, secvp, cool, qvect, charlie, robotics
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, sant1, volei1, ab3, camion1, aranjare, popas, reactivi, mesaj2, dp, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, micro, triburi, testament, 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, sant1, 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, 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
surse trimise | ajutor