Fişierul intrare/ieşire:secv3.in, secv3.outSursăpreONI 2004
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test0.125 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Secventa 3

Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite.
Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema!

Gigel este o persoana cu o imaginatie foarte bogata, mai ales cand doarme! Intr-o noapte a visat ca are de indeplinit o sarcina foarte bizara: trebuie sa aleaga o secventa (adica un subsir de elemente care apar pe pozitii consecutive in sirul initial) din N elemente pentru care se cunosc costul si timpul. Secventa aleasa trebuia sa fie de lungime minim L si maxim U, iar suma costurilor elementelor secventei impartita la suma timpurilor elementelor secventei sa fie maxima.

Cerinta

In scurt timp, visul lui Gigel s-a transformat intr-un cosmar deoarece nu poate sa rezolve sarcina! Scrieti un program care sa-l ajute!

Date de Intrare

Pe prima linie in fisierul de intrare secv3.in se afla numere N, L si U separate prin cate un spatiu. Pe cea de a doua linie se vor gasi N numere naturale reprezentand costurile elementelor secventei, iar pe cea de a treia linie se vor gasi N numere naturale reprezentand timpurile elementelor secventei.

Date de Iesire

Pe prima linie din fisierul de iesire secv3.out se va gasi un numar real cu prezicie de doua zecimale, reprezentand valoarea maxima a sumei costurilor elementelor din secventa impartita la suma timpurilor elementelor din secventa.

Restrictii si precizari

  • 1 ≤ L ≤ U ≤ N ≤ 30.000
  • Costul si timpul unui element sunt numere naturale din intervalul [1, 1.000]
  • Numarul scris in fisierul de iesire va fi considerat corect doar daca valoarea absoluta a diferentei dintre rezultatul tau si cel al comisiei este mai mica sau egala cu 10-2

Exemplu

secv3.insecv3.out
5 1 2
1 1 3 2 5
4 2 5 3 6
0.83
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content