Fișierul intrare/ieșire	praslea.in, praslea.out	Sursă	ONI 2014 clasa a 6-a
Autor	Cristina Iordaiche	Adăugată de	cris priboi radu bogdan • priboiradu
Timp de execuție pe test	0.5 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Prâslea ( clasa a 6-a )

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 L, în această ordine, despărțite prin câte un spațiu, având semnificația din enunț. Pe următoarele M linii, se afla câte două numere naturale P_i și L_i, 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 se afla 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

În 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

• 1 ≤ N ≤ 500000
• 1 ≤ M ≤ 10000
• M
• 1 ≤ L, L_i ≤ 4000000000
• 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

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.