# PBinfo #1127 – Praslea – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

A fost odată ca niciodată un împărat puternic  care avea o grădină minunată, situată pe un teren de formă dreptunghiulară din jurul palatului. În grădină creştea  un măr cu  mere de aur, dar împăratul nu a putut să se bucure vreodată de merele din pom deoarece grădina a fost mereu atacată de tâlhari şi merele au fost furate. Cu toate că aceasta a fost păzită zi şi noapte de cei mai viteji ostaşi din împărăţie, ei nu au putut face faţă tâlhăriilor. Deznădăjduit, împăratul şi-a pus în gând să taie pomul cu mere de aur, dar fiul său cel mic, Prâslea, l-a rugat să-l lase şi pe el să-şi încerce norocul. Prâslea a cugetat foarte bine la cele întâmplate şi a procedat astfel:


a delimitat în grădină, de-a lungul acesteia, N parcele alăturate, numerotate de la stânga la dreapta cu valori în ordine, de la 1 la N. Dintre acestea, a dat spre pază fraţilor şi verişorilor săi M parcele, iar restul de N-M parcele oştenilor din împărăţie. Cele N-M parcele date oştenilor sunt identice şi au fiecare lăţimea L.
a măsurat distanţa D la care se află pomul cu merele de aur faţă de marginea din stânga a grădinii, pentru a întări chiar el paza parcelei în care e situat acesta.

Cerinţă

a) Cunoscând lăţimea fiecărei parcele, determinaţi cel mai mare număr de parcele alăturate, de lăţime L fiecare, date spre pază oştenilor ; 
b) Determinaţi numărul de ordine al parcelei în care se află pomul cu merele de aur. 

Date de intrare
Fișierul de intrare praslea.in conține


pe prima linie trei numere naturale N, M şi L, în această ordine, despărţite prin câte un spaţiu, având semnificaţia din enunţ;
pe următoarele M linii, câte două numere naturale Pi şi Li, despărţite prin câte un spaţiu, reprezentând numărul de ordine, respectiv lăţimea fiecărei parcele dintre cele M, dată spre pază fraţilor şi verişorilor;
pe următoarea linie un număr natural D, care reprezintă distanţa la care se află pomul cu merele de aur faţă de marginea din stânga a grădinii.

Date de ieșire
Fișierul de ieșire praslea.out va conține pe prima linie un singur număr natural determinat conform cerinţei a), iar pe cea de-a doua linie a fişierului un singur număr natural determinat conform cerinţei b).

Restricții și precizări

1 ≤ N ≤ 500 000 şi 1 ≤ M ≤ 10 000 şi M<N;
1 ≤ L,Li ≤ 4 000 000 000;
Nicio parcelă dintre cele M nu are lăţimea egală cu L;
Dacă  D este exact  pe linia ce desparte două parcele alăturate se consideră că pomul e situat în parcela din stânga
Pentru rezolvarea corectă a cerinţei a) se acordă 20% din punctajul fiecărui test, iar pentru rezolvarea corectă a cerinţei b) se acordă 80% din punctajul fiecărui test.

Exemplu:
praslea.in

8 3 2
2 1
5 4
1 1
7
praslea.out

3
5
Explicație
Sunt 8 parcele: 3 dintre ele au fost împărţite fraţilor şi verişorilor. Parcelele rămase pentru oşteni au toate lăţimea 2. Dintre cele 3 parcele: parcela 2 are lăţimea 1, parcela 5 are lăţimea 4 şi parcela 1 are lăţimea 1. Pomul cu mere de aur se află la distanţa 7  faţă de marginea din stânga a grădinii.

Sunt 3 parcele alăturate care au lăţimea egală cu 2 (parcelele numerotate cu 6,@7@ şi 8).

Pomul se află în parcela cu numărul de ordine 5.

## Cod sursă C++

```cpp
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
struct parcela{ unsigned int indice, latime;
              } C[10002];
ifstream fin("praslea.in");
ofstream fout("praslea.out");
long long N,L,M,P,indice_precedent,alaturate,max_parcele,Pom;
bool cmp(parcela a,parcela b)
{
return a.indice<b.indice;
}
int main()
{
int i,ok=0;
fin>>N>>M>>L;
float x;
//citirea datelor
for(i=0;i<M;++i)
fin>>C[i].indice>>C[i].latime;
M++;
C[M].indice=N+1;C[M].latime=0; //sortarea parcelelor in functie de indice
fin>>P;
sort(C,C+M,cmp);
max_parcele=N-C[M-1].indice;
i=0;
while(i<M)
{
    alaturate=C[i].indice-indice_precedent-1;
    max_parcele=max(max_parcele,alaturate);            //rezolvare cerinta a)
    if(!ok && P<=(alaturate*L))
       {Pom=indice_precedent+ceil((double)P/L);ok=1;} // pomul e inaintea parcelei curente
    else
    {
        if (alaturate>0) P=P-(alaturate)*L;
        if(!ok && P<=C[i].latime)                 //pomul e in parcela curenta
           {Pom=C[i].indice;ok=2;}
        else
         P=P-C[i].latime;                        // pomul e situat la dreapta parcelei curente
    }
    indice_precedent=C[i].indice;
    i++;
}
fout<<max_parcele<<'\n';
if(ok==0)
Pom=C[M-1].indice+ceil((double)P/L);  //pomul e situat la drapta ultimei parcele din cele M citite
fout<<Pom<<'\n';
return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1127)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1127/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1127/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)