Fişierul intrare/ieşire:pudge.in, pudge.outSursăFMI No Stress 9
AutorStelian ChichirimAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pudge

Pudge este pozitionat in punctul (X,Y) in plan si are un hook de latime D (D e par).
Acesta poate arunca hook-ul in orice punct (X0, 0), 0 <= X0 <= X intreg; timpul hook-ului sa ajunga pe axa Ox este egal cu lungimea segmentului format de pozitia lui Pudge si punctul in care arunca hook-ul.
Pe axa Ox sunt mai multi inamici, fiecare inamic este la o pozitie Pi si are o viteza constanta Vi pe unitate de timp (toti inamicii se misca pe axa Ox spre +infinit).
Daca pudge arunca hook-ul in punctul X0, acesta va prinde toti inamicii care sunt in intervalul [X0-D/2, X0+D/2] in momentul de timp in care hook-ul ajunge pe axa Ox.
Calculati numarul maxim de inamici pe care ii poate prinde pudge dintr-o aruncare a hook-ului.

Date de intrare

Fişierul de intrare pudge.in contine pe prima linie X, Y, D si N, care semnifica numarul de inamici.
Urmeaza N linii, fiecare avand 2 numere Pi, pozitia initiala a inamicului, si Vi, viteaza acestuia.

Date de ieşire

În fişierul de ieşire pudge.out se va afisa numarul maxim de inamici pe care ii poate prinde pudge.

Restricţii

  • 1 <= N <= 100.000
  • 0 <= X, Y, D <= 108, numere intregi
  • 0 <= Pi <= 108 intreg, 0 <= Vi <= 10 intreg, pentru fiecare inamic.
  • 0 <= X0 <= X
  • Pudge arunca hook-ul la momentul 0.
  • Pentru 20% din punctaj Vi = 0 pentru toti inamicii si 0 <= X, Y, D, Pi <= 106.
  • Pentru alte 20% din punctaj 1 <= N <= 1000 si 0 <= X, Y, D, Pi <= 1000.
  • Pentru alte 40% din punctaj 0 <= X, Y, D, Pi <= 106.
  • Pentru alte 20% din punctaj restrictiile initiale.

Exemplu

pudge.inpudge.out
10 2 4 5
12 1
2 2
7 0
4 1
3 4
3
100 5 20 6
15 1
50 0
20 2
70 1
50 5
30 2
2

Explicaţie

Pentru primul exemplu:

Pudge poate arunca hook-ul in punctul 8 pentru a prinde 3 inamici. Hook-ul va ajunge pe axa Ox in punctul 8 la timpul  \sqrt{8} .

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?