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=0, iar punctul unde este finalizat studiul are coordonata Xf. Robotul se deplasează cu viteză constantă și parcurge o unitate de drum într-o unitate de timp.

Cercetătorii au stabilit N zone ce fac posibilă recepția datelor transmise de robot către satelit. Fiecare zonă este definită prin pereche X[i] L[i] (X[i] – coordonata de început a zonei i, L[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 D.

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 T unității de timp consumate.

Cerința

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

Date de intrare

Fișierul de intrare curiosity2.in conţine pe prima linie patru numere naturale Xf, D, T, N cu semnificația din enunț. Pe următoarele N linii descrierea zonelor: X[i] L[i], numere naturale, unde X[i] reprezintă coordonata de început a zonei i, iar L[i] lungimea zonei.

Date de ieșire

Fișierul de ieșire curiosity2.out va 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

1 ≤ N ≤ 100000
1 ≤ D ≤ 10⁶
1 ≤ T ≤ 10⁹
0 < Li, Xf ≤ 10⁹
0 ≤ Xi ≤ Xf
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 Xf robotul trebuie să finalizeze transmisiile;
Zonele sunt date în ordine crescătoare a distanței față de origine.

Exemplu

curiosity2.in

curiosity2.out

Explicație

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema curiosity2:

#include<bits/stdc++.h>
using namespace std;

typedef pair <int, int> seg;
const int maxn = 1e5 + 10;
int l[maxn], r[maxn];
seg f0[maxn], f[maxn];

seg bsd(seg a, seg b) {
    if(a.first > b.first || (a.first == b.first && a.second < b.second))
        return a;
    return b;
}
int query(int x, int n) {
    return lower_bound(r + 1, r + 1 + n, x) - r;
}
void solve() {
    int j, n, w;
    int L, d, t;
    ifstream cin ("curiosity2.in");
    ofstream cout ("curiosity2.out");
    cin >> L >> d >> t >> n;
    for (int i = 1; i <= n; i++){
        cin >> l[i] >> w;
        r[i] = l[i] + w;
    }
    l[n + 1] = L + 1;
    r[n + 1] = L + 2;
    for (int i = 1; i <= n; i++) {
        f0[i] = bsd(f0[i], f0[i - 1]);
        f[i] = bsd(f[i], {f0[i].first + (r[i] - l[i]) / d, l[i] + (r[i] - l[i]) / d * d });
        int t0 = f[i].second + t;
        j = query(t0, n + 1);
        if(j > n) continue;
        if(l[j] >= t0) {
            f0[j] = bsd(f0[j], {f[i].first, t0 });
            continue;
        }
        f[j] = bsd(f[j], {f[i].first + (r[j] - t0) / d, t0 + (r[j] - t0) / d * d});
        f0[j + 1] = bsd(f0[j + 1], {f[i].first, t0 });
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, f[i].first);
    cout << ans << endl;
}
int main() {
    solve();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2067 curiosity2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2067 curiosity2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2067 curiosity2