Diferente pentru problema/viteze intre reviziile #16 si #54

Diferente intre titluri:

viteze
Viteze

Diferente intre continut:

== include(page="template/taskheader" task_id="viteze") ==
$K0Kalaru 47$ a reusit anul trecut sa ia locul $2$ la JBOI (foarte aproape sa ia maxim) obtinand astfel bani si faima. Ca orice cocalar care se respecta, acesta si-a cumparat un BMW pentru a nu mai fi nevoit sa imprumute calul vecinului. Din pacate, acesta inca sta destul de prost cu actele si de aceea nu vrea sa fie tras pe dreapta de catre politia rutiera (amenda nu este o problema, data fiind averea sa inestimabila).
$K0Kalaru 47$ a reusit anul trecut sa ia locul $2$ la JBOI (foarte aproape sa ia *MAXIM*), obtinand astfel bani si faima. Ca orice cocalar care se respecta, acesta si-a cumparat un BMW pentru a nu mai fi nevoit sa imprumute calul vecinului. Din pacate, acesta inca sta destul de prost cu actele si de aceea nu vrea sa fie tras pe dreapta de catre politia rutiera (amenda nu este o problema, data fiind averea sa inestimabila).
Anul acesta, pentru a ajunge la JBOI, cocalarul va folosi o autostrada care porneste fix din curtea casei sale si se termina la hotelul unde va avea loc balcaniada. Autostrada este impartita in $N$ portiuni, fiecare cu propria ei limita de viteza, portiunile fiind numerotate cu numere de la $1$ la $N$. Toate portiunile au lungime de o unitate, iar vitezele si limtele acestora sunt exprimate in unitati pe secunda.
Anul acesta pentru a ajunge la JBOI cocalarul va folosi o autostrada care porneste fix din curtea casei sale (vorba poetului - de la kilometrul 0 al fiţelor) si se termina la hotelul unde va avea loc balcaniada. Autostrada este impartita in $N$ portiuni, fiecare cu propria ei limita de viteza, portiunile fiind numerotate cu numere naturale de la $1$ la $N$. Toate portiunile au lungimea de o unitate, iar vitezele si limtele acestora sunt exprimate in unitati pe secunda.
De asemenea, conditiile meteorolgice impun si ele anumite restrictii: la trecerea de pe o portiune pe alta exista o limita de acceleratie/franare pe care $K0Kalaru 47$ trebuie sa o respecte pentru a nu derapa (aceasta limita reprezinta practic diferenta maxima dintre vitezele cocalarului pe portiuni consecutive ale autostrazii). <tex>delta_i</tex> reprezinta diferenta maxima de viteze intre portiunea $i - 1$ si $i$ (caz particular face <tex>delta_1</tex> care este tot o limitare a primei viteze, dat fiind faptul ca pe portiunea imaginara $0$, cocalarul are viteza de $0$, <tex>lim_1</tex> reprezentand acceleratia maxima la momentul plecarii). Pentru simplitate in cadrul unei portiuni, cocalarul isi va mentine viteza constanta.
De asemenea, conditiile meteorolgice impun si ele anumite restrictii: la trecerea de pe o portiune pe alta exista o limita de acceleratie/franare pe care $K0Kalaru 47$ trebuie sa o respecte pentru a nu derapa (aceasta limita reprezinta practic diferenta maxima dintre vitezele cocalarului pe portiuni consecutive ale autostrazii). <tex>delta_i</tex> reprezinta diferenta maxima de viteze intre portiunea $i - 1$ si $i$ (caz particular face <tex>delta_1</tex> care este tot o limitare a primei viteze, dat fiind faptul ca pe portiunea imaginara $0$, cocalarul are viteza de $0$, <tex>lim_1</tex> reprezentand acceleratia maxima la momentul plecarii). Pentru simplitate, in cadrul unei portiuni cocalarul isi va mentine viteza constanta.
Ca de obicei, voi trebuie sa-l ajutati pe cocalar, calculandu-i vitezele optime astfel incat sa ajunga cat mai devreme la jboi. Timpul total este calculat ca fiind <tex>1 / v_1 + 1 / v_2 + ...1 / v_N </tex>.
Ca de obicei, voi trebuie sa-l ajutati pe cocalar, calculandu-i vitezele optime astfel incat sa ajunga cat mai devreme la JBOI. Timpul total este calculat ca fiind <tex>\frac{1}{v_1} + \frac{1}{v_2} + ... + \frac{1}{v_N} </tex>.
h2. Date de intrare
h2. Date de ieşire
În fişierul de ieşire $viteze.out$ se vor afise pe prima si singura linie N numere naturale nenule reprezentand vitezele pe cu cate va alege $K0Kalaru 47$ sa se deplaseze pe fiecare portiune in parte.
În fişierul de ieşire $viteze.out$ se vor afise pe prima si singura linie N numere naturale nenule reprezentand vitezele cu care $K0Kalaru 47$ va alege sa se deplaseze pe fiecare portiune in parte.
h2. Restricţii
* **Atentie!** Fiecare subtask are testele grupate!
* **Subtask 1 (10 puncte)**: $1 &le; N &le; 10$ si <tex> lim_1 * lim_2 * ... * lim_{$N$} </tex> &le; 500000
* **Subtask 2 (20 puncte)**: $1 &le; N &le; 100$ si <tex> lim_i </tex> &le; 100
* **Subtask 3 (20 puncte)**: $1 &le; N &le; 1000$ si <tex> lim_i </tex> &le; 1000
* **Subtask 4 (30 puncte)**: $1 &le; N &le; 100000$ si <tex> lim_i </tex> &le; 10^9^
* **Subtask 5 (20 puncte)**: $1 &le; N &le; 1000000$ si <tex> lim_i </tex> &le; 10^9^
* Cocalarul va sfatuieste sa ganditi problema gandindu-va ca sunteti in locul lui.
* <tex> 1 \leq lim_i \leq 10^9 </tex> (pentru {$1 &le; i &le; N$})
* <tex> 0 \leq delta_i \leq 10^9 </tex> (pentru {$1 &le; i &le; N$})
 
* Se garanteaza ca exista solutie.
 
* Cocalarul va sfatuieste sa ganditi problema ca si cum ati fi in locul lui.
 
* **Subtask 1 (10 puncte)**: $1 &le; N &le; 10$ si <tex> lim_1 \cdot lim_2 \cdot ... \cdot lim_{$N$} \leq 500.000 </tex> (Feedback testul $2$)
* **Subtask 2 (20 puncte)**: $1 &le; N &le; 100$ si <tex> lim_i \leq 100 </tex>  (Feedback testul $6$)
* **Subtask 3 (20 puncte)**: $1 &le; N &le; 1.000$ si <tex> lim_i \leq 1.000 </tex> (Feedback testul $10$)
* **Subtask 4 (30 puncte)**: $1 &le; N &le; 100.000$ si <tex> lim_i \leq 10^9 </tex>  (Feedback testul $16$)
* **Subtask 5 (20 puncte)**: $1 &le; N &le; 1.000.000$ si <tex> lim_i \leq 10^9</tex> (Feedback testul $20$)
 
* *ATENŢIE! Se recomandă parsarea fişierelor $viteze.in$ şi $viteze.out$ pentru obţinerea scorului maxim. Puteţi folosi codul oferit de noi pe siteurile 'in':http://www.infoarena.ro/parsare-fisier-intrare şi 'out':http://www.infoarena.ro/parsare-fisier-iesire (atât pentru utilizatorii de C++ şi sintaxă similară cu $fstream, cât şi pentru iubitorii de C pur$)*
 
h2. Exemplu
table(example). |_. viteze.in |_. viteze.out |
h3. Explicaţie
Sirul optim de viteze este unic determinat in exemplu, reprezentand pentru $K0Kalaru 47$ o strategie prin care va ajunge la JBOI in $1/3 + 1/3 + 1/1 + 1/2 = 2.1(6)$ secunde. Acesta nu va derapa deoarece $|0 - 3| &le; 5, |3 - 3| &le; 3, |3 - 1| &le; 2$ si $|1 - 2| &le; 1$. De asemenea, cocalarul nu va fi depasi limita de viteza la niciun moment deoarece $3 &le; 3, 3 &le; 4, 1 &le; 1$ si $2 &le; 3$
Sirul optim de viteze este unic determinat in exemplu, reprezentand pentru $K0Kalaru 47$ o strategie prin care va ajunge la JBOI in $1 / 3 + 1 / 3 + 1 / 1 + 1 / 2 = 2.1(6)$ secunde. Acesta nu va derapa deoarece $|0 - 3| &le; 5, |3 - 3| &le; 3, |3 - 1| &le; 2$ si $|1 - 2| &le; 1$. De asemenea, cocalarul nu va depasi limita de viteza la niciun moment deoarece $3 &le; 3, 3 &le; 4, 1 &le; 1$ si $2 &le; 3$
== include(page="template/taskfooter" task_id="viteze") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.