Simulation - Lot 2017 Baraj 4 Juniori | curiosity2

This was the problem page during the contest. Access the current page here.
Time limit: 0.04s Memory limit: 128MB Input: curiosity2.in Output: curiosity2.out

Aventura robotului Curiosity pe Marte continuă. Robotul se deplasează de-a lungul unei axe de coordonate Ox. Punctul de plecare în incursiune are coordonata x=0x = 0, iar punctul unde este finalizat studiul are coordonata XfX_f. Robotul se deplasează cu viteză constantă și parcurge o unitate de drum într-o unitate de timp.

Cercetătorii au stabilit NN zone ce fac posibilă recepția datelor transmise de robot către satelit. Fiecare zonă este definită prin pereche XiX_i, LiL_i (XiX_i – coordonata de început a zonei ii, LiL_i – lungimea zonei). Zonele nu interferează (nu au puncte comune). Datele sunt transmise în pachete de dimensiune fixă, iar durata de transmisie a unui pachet este DD.

Pe parcursul unei zone robotul poate transmite unul sau mai multe pachete de date. După ce a finalizat transmisia unui pachet, robotul poate continua transmisia unui alt pachet, dacă este posibil (nu este acceptată transmiterea unui pachet incomplet), sau poate întrerupe transmisia. După întrerupere, robotul poate relua transmisia după cel puțin de TT unității de timp consumate.

Cerinţă

Să se determine numărul maxim de pachete de date ce pot fi transmise de către robot satelitului.

Date de intrare

Fişierul curiosity2.in conţine pe prima linie patru numere naturale XfX_f, DD, TT, NN cu semnificația din enunț. Pe următoarele NN linii descrierea zonelor: XiX_i, LiL_i, numere naturale, unde XiX_i reprezintă coordonata de început a zonei ii, iar LiL_i lungimea zonei.

Date de ieșire

Fişierul curiosity2.out conţine pe o singură linie un singur număr natural ce reprezintă numărul maxim de pachete de date ce pot fi transmise de către robot.

Restricții și precizări

  • 1N100 0001 \leq N \leq 100 \ 000;
  • 1D1061 \leq D \leq 10^6;
  • 1T1091 \leq T \leq 10^9;
  • 0<Li,Xf1090 < L_i, X_f \leq 10^9;
  • 0XiXf0 \leq X_i \leq X_f;
  • Transmisiile pot fi efectuate doar în zonele specificate;
  • Transmisia unui pachet începe și se termină în coordonate întregi;
  • Robotul poate începe transmisia unui pachet numai dacă anterioara transmisie s-a finalizat;
  • Când atinge coordonata XfX_f robotul trebuie să finalizeze transmisiile;
  • Zonele sunt date în ordine crescătoare a distanței față de origine.

Exemplu

curiosity2.in

16 2 3 3
2 5
8 4
14 3

curiosity2.out

4

Explicație

Log in or sign up to be able to send submissions!