vanatoare

Vanatoare

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

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

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

h2. Date de iesire

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

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 ≤ 20$
* $1 < T < 2^32^$

* $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 se poate afisa oricare

* Daca exista mai multe solutii optime se poate afisa oricare

h2. Exemplu

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

2915