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

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


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

Jean-Luc Picard, căpitanul navei spaţiale Enterprise, a constatat că în vecinătatea navei sale au apărut n nave borgiene. Distanţele dintre acestea şi nava Enterprise sunt d1, d2, ..., dn. Navele borgiene nu se deplasează unele în raport cu altele şi nici în raport cu nava Enterprise. Poziţiile în spaţiu ale celor n nave borgiene şi poziţia navei Enterprise sunt distincte două câte două (nu există două nave care să ocupe acelaşi punct în spaţiul tridimensional).

La un moment dat, toate cele n nave borgiene declanşează simultan atacul, lansând câte un proiectil în direcţia navei Enterprise. Pereţii navei Enterprise sunt rezistenţi la asemenea atacuri, însă căpitanul decide să distrugă un număr maxim de proiectile cu ajutorul armei laser. Cele n proiectile se deplasează cu vitezele constante v1, v2, ..., vn exprimate în metri pe secundă. Căpitanul Jean-Luc Picard are la dispoziţie o armă laser cu care poate distruge pe rând câte un proiectil. Arma poate fi orientată instantaneu spre oricare navă borgiană. Arma laser poate executa oricâte trageri începând cu momentul declanşării atacului, dar după fiecare tragere are nevoie de t secunde pentru a se reîncărca cu energie. În acest interval de timp nu se poate efectua o altă tragere. Orientarea armei laser spre un anumit proiectil nu consumă timp. De asemenea, timpul scurs între momentul tragerii şi distrugerea proiectilului vizat este zero. Căpitanul nu ratează ţinta niciodată, iar proiectilele care reuşesc să lovească nava Enterprise nu-l pot împiedica pe căpitanul Picard să continue să tragă asupra altor proiectile aflate în mişcare.

Cerinţă

Să se găsească numărul maxim de proiectile care pot fi distruse cu arma laser.

Date de intrare

Fişierul de intrare startrek.in conţine pe prima linie numerele naturale n şi t, reprezentând numărul de nave borgiene, respectiv timpul de reîncărcare a armei laser cu energie. Pe linia a doua, sunt n numere naturale d1 d2 ... dn reprezentând distanţele la care se găsesc navele borgiene faţă de nava Enterprise. Pe linia a treia se găsesc n numere naturale v1 v2 ... vn reprezentând vitezele de deplasare ale celor n proiectile.

Date de ieşire

Fişierul de ieşire startrek.out va conţine un număr natural p, reprezentând numărul maxim de proiectile distruse.

Restricţii

2 <= n <= 4000
1 <= d1, d2, ..., dn <= 10000
1 <= v1, v2, ..., vn, t <= 1000

Dacă momentul în care un proiectil ar trebui să lovească nava coincide cu momentul în care se trage cu arma laser asupra lui, se consideră că Enterprise distruge acel proiectil.
Dacă viteza unui proiectil este v, atunci în timpul t, acesta străbate distanţa d = v*t

Exemple

startrek.instartrek.outExplicaţii
3 4 4 3 6 2 1 1 2 Se distruge proiectilul 1, după care proiectilul 2 loveşte nava Enterprise, apoi se distruge proiectilul 3.
4 2 2 5 8 5 1 3 2 5 3 Se distruge proiectilul 4, după care proiectilul 2 loveşte nava Enterprise, apoi se distruge proiectilul 1, iar apoi se distruge proiectilul 3.

autor: Prof. Suzana Gălăţan
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la OJI 2009: reteta, expresie, insule, factori, grad, ruleta2, vecini2, placare, 235
De acelaşi autor: patrate2, rezervatie, cluburi, smin, papusa, flori1
Despre Greedy: lac, sumdif, checkin, baby, 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, 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, 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, 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
surse trimise | ajutor