vanatoare

Vanatoare

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

Poveste si cerinta...

Pe un cunoscut domeniu de vanatoare privat a inceput vanatoarea de mistreti. Domeniul este liniar si are lungimea de $T$ unitati. Astfel, el poate fi considerat ca un segment pe axa Ox a sistemului de coordonate, intre punctele de coordonate $0$ si {$T$}. Sunt $N$ mistreti care trebuie vanati. Fiecare mistret este caracterizat de o pereche de numere naturale {$(c{~i~} v{~i~})$}, cu {$0 &le; c{~i~} < v{~i~}$}, care are urmatoarea semnificatie: la momentul $0$ (care reprezinta inceputul vanatorii) mistretul $i$ se afla la coordonata {$c{~i~}$} pe axa si alearga cu o viteza constanta de {$v{~i~}$} metri pe secunda. Aceasta inseamna ca la secunda {$p$} ( {$p &ge; 0$} ) mistretul se va afla la coordonata {$c{~i~} + v{~i~} * p$}.
Desi cei care participa la vanatoare sunt foarte bogati, ei tin cont de resursele de care dispun si doresc sa impuste mistretii cu numar minim de vanatori. Un vanator se pozitioneaza la o coordonata numar natural ce se afla in interiorul domeniului (deci un vanator se poate pozitiona intre orice coordonata intre $0$ si {$T$} inclusiv) si va impusca toti mistretii care trec prin dreptul sau la momente intregi de timp. Sa se precizeze numarul minim de vanatori necesari pentru a impusca toti mistretii, precum si pozitiile unde acestia trebuie sa se pozitioneze.

h2. Date de intrare

Fisierul de intrare $vanatoare.in$ ...

Fisierul de intrare $vanatoare.in$ contine pe prima linie numerele naturale $N$ si $T$, separate printr-un spatiu. Fiecare din urmatoarele $N$ linii contin descrierea cate unui mistret. Astfel, linia $i+1$ va contine perechea de numere naturale {$(c{~i~} v{~i~})$}, cu semnificatia din enunt.

h2. Date de iesire

In fisierul de iesire $vanatoare.out$ ...

In fisierul de iesire $vanatoare.out$ se va afisa pe prima linie numarul minim $MIN$ de vanatori necesari pentru a impusca cei $N$ mistreti. A doua linie contine exact $MIN$ numere naturale cuprinse intre $0$ si {$T$}, indicand pozitiile celor $N$ vanatori.

h2. Restrictii

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

* $1 ≤ N ≤ 16$
* $1 ≤ T ≤ 2 000 000 000$
* Pentru orice pereche din fisierul de intrare este indeplinita relatia: {$0 &le; c{~i~} < v{~i~} &le; 200 000 000$}
* Se considera ca un vanator poate impusca mai multi mistreti simultan
* Daca exista mai multe solutii optime se poate afisa oricare

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

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

|3 10
3 5
1 3
2 3
|2
7 8

|
h3. Explicatie

...

Primul vanator va impusca al doilea mistret in secunda {$2$}. Al doilea vanator va impusca mistretul $1$ in secunda {$1$}, iar cel de-al treilea mistret in secunda {$2$}. Astfel sunt impuscati toti mistretii. Cei $3$ mistreti nu pot fi impuscati cu un singur vanator, deci $2$ vanatori reprezinta solutia optima.

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

2915