== include(page="template/taskheader" task_id="bombe") ==
Poveste şi cerinţă...
Ţara ta este în război, iar tu eşti şeful consiliului de apărare a ţării. Tocmai ai primit un mesaj îngrijorător: $N$ nave inamice au invadat spaţiul marin al ţării. Fiecare dintre cele $N$ nave se mişcă în linie dreaptă (mai exact de-a lungul axei $Ox$ ), cu viteză constantă.
Prin satelit ţi-a fost transmisă o hartă, pe care sunt marcate poziţiile navelor la momentul $0$ (distanţa faţă de origine exprimată în metri). Ai observat că la momentul $0$ toate navele se află în puncte de coordonate întregi.
Ai posibilitatea de a bombarda navele inamice utilizând un sistem special. Sistemul permite detonarea unor bombe, dar este posibilă doar detonarea tuturor bombelor exact în acelaşi timp. Când este detonată o bombă ea va distruge toate navele situate la o distanţă ≤ $R$ metri (raza de acţiune a bombei).
h2. Cerinţă
Misiunea ta este să detonezi un număr minim de bombe astfel încât să fie distruse toate navele. De asemenea, doreşti să detonezi acel număr minim de bombe în timpul cel mai scurt.
h2. Date de intrare
Fişierul de intrare $bombe.in$ ...
Fişierul de intrare $bombe.in$ conţine pe prima linie un număr natural $N$, reprezentând numărul de nave, urmat de un număr real $R$, reprezentând raza de acţiune a bombelor. Pe următoarele $N$ linii sunt descrise cele $N$ nave, câte o navă pe o linie. Pe o linie ce descrie o navă vor fi scrise două numere separate prin spaţiu $x$ $v$, unde $x$ reprezintă un număr natural indicând poziţia navei la momentul $0$, iar $v$ este un număr real indicând viteza (în $m/s$ ) cu care se deplasează nava. Dacă viteza este pozitivă, deplasarea navei se realizează în sensul axei $Ox$, iar dacă viteza este negativă, deplasarea navei se realizează în sensul invers al axei $Ox$.
h2. Date de ieşire
În fişierul de ieşire $bombe.out$ ...
Fişierul de ieşire $bombe.out$ va conţine o singură linie pe care vor fi scrise două numere separate prin spaţiu $nrmin tmin$, unde $nrmin$ reprezintă numărul minim de bombe necesare pentru distrugerea tuturor navelor, iar $tmin$ este timpul minim (exprimat în secunde) la care pot fi detonate cele $nrmin$ bombe pentru a distruge toate navele. Timpul va fi afişat cu $3$ zecimale.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 300$
* $0 < R ≤ 5$
* $x ≤ 1 000 000$ , pentru orice $1 ≤ i ≤ N$
* $ |v| ≤ 100$, pentru orice $1 ≤ i ≤ N$
* Este posibil ca la un moment dat două nave să se afle în acelaşi punct, dar niciodată nu vor exista $3$ nave în acelaşi punct.
* Timpul minim afişat este considerat corect dacă diferă prin cel mult 0.01 de timpul minim corect.
h2. Exemplu
table(example). |_. bombe.in |_. bombe.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 0.25
2 0.5
3 -1
5 -1
5 0.333
8 0.5
10 -0.2
| 4 0.333
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="bombe") ==
