Cerința

Iulică este acasă și trebuie să ajungă la patinoar. Patinoarul se află la exact d km de mers pe jos, astfel încât, dacă am considera un sistem de coordonate, casa lui Iulică se află în punctul 0 și patinoarul se află în punctul d.

Între parc și patinoar există k magazine din care se poate cumpăra pâine, magazine situate la a[i] km (1 <= i <= k) față de casa lui Iulică, în aceeași direcție în care se află patinoarul. Fiind foarte departe, Iulică nu poate ajunge foarte repede la patinoar. Astfel, înainte să plece, mama lui Iulică îi da un ghiozdan care poate căra cel mult g pâini, inițial cu g pâini în el. Știind că Iulică poate mânca o pâine sau poate să stea nemâncat pe parcursul unui km, și că poate sta nemâncat maximum t km pe întreg traseul, aflați capacitatea minimă g pe care o poate avea ghiozdanul, astfel încât Iulică să poată ajunge la patinoar fără să moară de foame. Iulică îşi poate umple ghiozdanul de la fiecare magazin gratuit.

Date de intrare

Fișierul de intrare ghiozdan.in conține pe prima linie trei numere naturale d, k, t, separate prin câte un spațiu, fiecare având semnificațiile din enunț. Linia a doua conține k numere naturale a[i] (1 <= i <= k), în ordine crescătoare, reprezentând distanța de la casa lui Iulică la magazinul i.

Date de ieșire

Fișierul de ieșire ghiozdan.out conține pe prima linie un singur număr natural reprezentând capacitatea g minimă a ghiozdanului.

Restricții și precizări

1 <= d <= 10000000
0 <= k <= 100000
1 <= a[i] <= d, 1 <= i <= k
0 <= t <= d
20% din teste vor avea valoarea t = 0

Exemplu

ghiozdan.in

6 1 2
3

ghiozdan.out

Explicație

Se observă că dacă ghiozdanul putea căra maximum o pâine, Iulică nu ar fi putut ajunge la patinoar.

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

#include <bits/stdc++.h>

using namespace std;
ifstream f("ghiozdan.in");
ofstream g("ghiozdan.out");

const int NMax = 100002;

int d,k,t;
int a[NMax];

bool OK(int dim){   ///functia care verifica daca Iulica poate
                    ///lua un ghiozdan de capacitate dim pentru a ajunge la destinatie
                    ///Returneaza 1 daca este posibil si 0 daca nu poate ajunge la destinatie
    int drum_ramas = t;///variabila care retine cati km mai poate merge Iulica nemancat,
                       ///initial, aceasta avand valoarea t
    for(int i = 1; i <= k; ++i)
        if(a[i] - a[i - 1] > dim)
            drum_ramas -= (a[i] - a[i - 1] - dim);

    if(drum_ramas < 0)
        return 0;
    return 1;
}
int cautbin(int lo,int hi){
    int mid;
    while(lo <= hi){
        mid = (lo + hi) / 2;

        int ok1 = OK(mid);
        int ok2 = OK(mid - 1);

        if(ok1 == 1 && ok2 == 0){///daca se poate ajunge la patinoar cu g = mid si nu se poate cu g = mid - 1
                                ///insemna ca mid este valoarea minima pentru g
            return mid;
        }else
        if(ok1 == 1){
            hi = mid - 1;
        }else
        if(ok2 == 0){
            lo = mid + 1;
        }
    }
    return 0;
}
int main()
{
    f >> d >> k >> t;   /// se citesc datele
    a[0] = 0;           ///se pune pe pozitia zero, casa lui Iulica
    for(int i = 1; i <= k; ++i)
        f >> a[i];      ///se citesc magazinele
    a[++k] = d;         ///se adauga pozitia patinoarului

    int G = cautbin(0,d);
    g << G << '\n';
    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 #2131 Ghiozdan

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