Misiunea robotului Curiosity este de-a trimite imagini și informații către satelitul plasat pe orbita planetei Marte. Zona de explorare a robotului este de-a lungul unei axe de coordonate Ox. Robotul este înzestrat cu o baterie solară de capacitate energetică maximă C și consumă pentru fiecare unitate de drum parcurs o unitate de energie. Coordonata punctului de plecare al incursiunii robotului (raportată la origine x=0) este Xs, iar punctul unde este finalizat studiul are coordonata Xf.
Totodată, cercetătorii au stabilit N puncte ce fac posibilă încărcarea bateriilor robotului, numerotate de la 1 la N. În funcție de intensitatea luminii solare primite, reflectată în durata de încărcare a bateriei, punctele de încărcare sunt de trei tipuri: tipul 1–intensitate minimă/timp de încărcare mare, tipul 2–intensitate medie/timp de încărcare mediu, tipul 3–intensitate maximă/timp de încărcare scurt. Altfel, fiecare punct de încărcare i este descris prin perechea t[i] x[i], adică tipul de încărcare, respectiv poziția acestuia pe axă. În orice punct de încărcare robotul poate decide dacă încarcă sau nu bateria, cu unități de energie, nu mai mult decât capacitatea maximă. Robotul se poate deplasa dintr-un punct atât în stânga cât și în dreapta pe axă.
Pentru a scurta durata parcurgerii distanței către punctul final se dorește determinarea unei strategi optime a opririlor pentru încărcarea bateriilor, astfel încât cantitatea totală de energie încărcată în puncte de tipul 1 să fie minimă. În cazul în care sunt mai multe strategii de oprire pentru care cantitatea totală de energie încărcată în puncte de tipul 1 este minimă, atunci se va alege strategia pentru care cantitatea totală de energie încărcată în puncte de tipul 2 să fie minimă.

Cerința

Dacă se cunosc Xs, Xf, C, precum și descrierea celor N puncte de încărcare să se determine o strategie de deplasare între coordonatele Xs și Xf, optimă din punct de vedere al timpului necesar încărcării bateriilor.

Date de intrare

Fișierul de intrare curiosity.in conţine pe prima linie patru numere naturale Xs, Xf, C, N cu semnificația din enunț. Pe următoarele N linii este descrierea punctelor de oprire: t[i] x[i], unde t[i] reprezintă tipul de încărcare al punctului i, iar x[i] poziția acestuia pe axă.

Date de ieșire

Fișierul de ieșire curiosity.out Fişierul curiosity.out conţine pe o singură linie două numere naturale despărțite printr-un spațiu, ce reprezintă cantitatea totală minimă de energie încărcată în puncte de tipul 1, respectiv cantitatea totală minimă de energie încărcată în puncte de tipul 2. Dacă nu există soluție se va afișa valoarea -1.

Restricții și precizări

1 ≤ N ≤ 100000
1 ≤ C ≤ 1000
1 ≤ t[i] ≤ 3; -1000000 ≤ x[i] ≤ 1000000
-1000000 ≤ Xs < Xf ≤ 1000000. Acestea pot coincide cu coordonatele punctelor de încărcare;
Punctele de încărcare sunt distincte. Coordonatele punctelor sunt de tip întreg;
Punctele de încărcare sunt date în ordine crescătoare
Atenție, în momentul plecării din punctul Xs robotul este încărcat la capacitatea maximă C.

Exemplu

curiosity.in

curiosity.out

1 3

Explicație

Pe axa există n=4 puncte de încărcare. Robotul pleaca din punctul xs=1 și trebuie să ajungă în punctul xf=11. Inițial robotul are bateria încărcată la capacitatea maximă C=5 unități. Robotul oprește în punctul x=3. Pentru deplasarea din x=1 în x=3 a consumat 2 unități de energie. Încarcă bateria cu 1 unitate (tip 1). Bateria are în acest moment capacitatea de 4 unități, suficiente pentru a ajunge în punctul x=7 unde încarcă bateria cu 3 unități (tip 2). În punctul x=10 încarcă bateria cu 1 unitate (tip 3).

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 curiosity:

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

# define NMax 100003

vector <int> X[4];
int cost[4][NMax], cost_optim[4];
int Xs, Xf, C, n;

int main()
{
    freopen("curiosity.in", "r", stdin);
    freopen("curiosity.out","w", stdout);

    scanf("%d%d%d%d", &Xs, &Xf, &C, &n);

    for(int i = 0; i < n; ++i){
        int t, x;
        scanf("%d%d", &t, &x);

        if(x >= Xf)
            continue;

        for(int j = 1; j <= t; ++j)
            X[j].push_back(x);
    }

    for(int t = 1; t <= 3; ++t){

        X[t].push_back(Xf);

        for(int j = X[t].size() - 2; j >= 0; j--)   /// ultima pozitie inainte de Xf
            cost[t][j] = cost[t][j + 1] + max(0, (X[t][j + 1] - X[t][j]) - C);
    }

    for(int t = 1; t <= 3; ++t) {

        int x = lower_bound(X[t].begin(), X[t].end(), Xs) - X[t].begin();

        cost_optim[t] = cost[t][x] + max(0, X[t][x] - Xs - C);
    }

    if(cost_optim[1] != 0)
        printf("-1\n");
    else
        printf("%d %d\n", cost_optim[2], cost_optim[3] - cost_optim[2]);
    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 #2052 curiosity

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2052 curiosity 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 #2052 curiosity