Fişierul intrare/ieşire:startrek.in, startrek.outSursăOJI 2009 clasa a 7-a
AutorSusana GalatanAdăugată deMarcelaMarcela Marcela
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Startrek (clasa a 7-a)

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

În 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 ≤ 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

Exemplu

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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici