Fişierul intrare/ieşire:vanatoare.in, vanatoare.outSursăpreONI 2008, Runda finala
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.35 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 (ci vi), cu 0 ≤ ci < vi, care are urmatoarea semnificatie: la momentul 0 (care reprezinta inceputul vanatorii) mistretul i se afla la coordonata ci pe axa si alearga cu o viteza constanta de vi metri pe secunda. Aceasta inseamna ca la secunda p ( p ≥ 0 ) mistretul se va afla la coordonata ci + vi * 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.

Date de intrare

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 (ci vi), cu semnificatia din enunt.

Date de iesire

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.

Restrictii

  • 1 ≤ N ≤ 16
  • 1 ≤ T ≤ 2 000 000 000
  • Pentru orice pereche din fisierul de intrare este indeplinita relatia: 0 ≤ ci < vi ≤ 200 000 000
  • Se considera ca un vanator poate impusca mai multi mistreti simultan
  • Daca exista mai multe solutii optime se poate afisa oricare

Exemplu

vanatoare.invanatoare.out
3 10
3 5
1 3
2 3
2
7 8

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content