Fişierul intrare/ieşire:bombe.in, bombe.outSursăLot Iasi 2008, Baraj 5
AutorAdrian Vladu, Mihai PatrascuAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.625 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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

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.

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.

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.

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.

Exemplu

bombe.inbombe.out
6 0.25
2 0.5
3 -1
5 -1
5 0.333
8 0.5
10 -0.2
4 0.333
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content