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

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


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

De-a lungul autostrăzii Soarelui sunt amplasaţi N senzori, numerotaţi în ordinea de la Bucureşti spre Constanţa, de la 1 la N. În timpul unei zile, senzorii înregistrează date în continuu, cu excepţia unui anumit interval de timp; mai exact, pentru orice senzor i există un interval [T1,i,T2,i) în care senzorul trebuie să trimita datele înregistrate către staţia centrală (acest interval de timp poate fi diferit de la un senzor la altul). Durata de transmitere a datelor senzorului i este di, iar datele trebuie să fie transmise într-un interval de timp



(momentul tstart,i nu este dat).
Datele unui senzor i au o valoare vi (în funcţie de importanţa strategică a amplasării senzorului). Senzorii comunică wireless cu staţia centrală, pe aceeaşi frecvenţă, şi de aceea pot apărea interferenţe la transmisia datelor senzorilor cu numere de ordine consecutive. Aşadar, intervalele de timp în care sunt transmise datele a doi senzori i şi i+1 (1≤i<N) trebuie să fie disjuncte:



Această restricţie poate conduce la situaţia neplacută în care nu toţi senzorii vor putea trimite datele către staţia centrală în intervalul de timp disponibil ([T1,i,T2,i) pentru senzorul i). În acest caz, se doreşte determinarea unei submulţimi de senzori care vor transmite datele către staţia centrală şi pentru care suma valorilor datelor transmise este maximă.

Cerinţă

Să se determine suma maximă a valorilor datelor transmise de o submulţime a celor N senzori, astfel încât transmisia datelor acestor senzori să respecte toate restricţiile specificate.

Date de intrare

Fişierul de intrare senzori.in conţine pe prima linie numărul natural N, reprezentând numărul de senzori. Fiecare dintre următoarele N linii conţine câte 4 numere întregi separate prin spaţiu: T1,i T2,i di vi; a i-a dintre aceste linii corespunde senzorului cu numărul i.

Date de ieşire

În fişierul de ieşire senzori.out veţi afişa suma maximă a valorilor datelor transmise de o submulţime de senzori care poate trimite datele catre staţia centrală respectând toate restricţiile specificate în enunţ.

Restricţii

1 ≤ N ≤ 2000
0 ≤ T1,i < T2,i ≤ 2000
1 ≤ di ≤ T2,i-T1,i
1 ≤ vi ≤ 10000

Exemple

senzori.insenzori.outExplicaţii
4 0 5 3 6 1 4 3 7 2 8 3 5 6 8 2 5 16 Senzorii care vor trimite date către staţia centrală sunt: 1, 3 şi 4. Senzorul 1 va trimite datele în intervalul [0,3), senzorul 3 va trimite datele în intervalul [3,6), iar senzorul 4 în intervalul [6,8). Valoarea totală a datelor trimise este 6+5+5=16.

autor: Mugurel Ionuţ Andreica
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot NT 2008: datorii, sub, tetris2, kinder, rev
De acelaşi autor: autobuze, bile, complex, balaur, vmem, kreg, ro, jobs, echipe, agitatie, center, algebra, tgraf, bcast, promo, asmax, sediu, granita, string, poligon1, csir, lsort, zoo, bombo, ab3, soc, rsp, tcast, tj, lanterna, base3, color, trans, ic, xp, v2d, ppcover, carray, asfalt1, module, gxor
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, 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