Bombe

bombe

== include(page="template/taskheader" task_id="bombe") ==

Ţ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.

Poveste şi cerinţă...

h2. Date de intrare

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$.

Fişierul de intrare $bombe.in$ ...

h2. Date de ieşire

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 rotunjit la $3$ zecimale.

În fişierul de ieşire $bombe.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 300$
* $0 < R &le; 5$
* $x &le; 1.000.000$ , pentru orice $1 &le; i &le; N$
* $|v| &le; 100$ , pentru orice $1 &le; i &le; 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.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. bombe.in |_. bombe.out |

| 6 0.25
  2 0.5
  3 -1
  5 -1
  5 0.333
  8 0.5
  10 -0.2
| 4 0.333

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="bombe") ==

3793