== include(page="template/taskheader" task_id="patrate3") ==
Poveste și cerință...
Anei îi place mult să se joace la calculator. Acum are un nou joc în care *n* blocuri orizontale formate din pătrate de latură 1, cad pe verticală. Suprafața de joc se reprezintă ca un tablou cu *L* ([*L*] > [*n*]) linii numerotate de la 1 la *L* și *C* coloane, numerotate de la 1 la *C*, ca în figură. Tabloul este constituit din *L* × *C* celule pătratice de latură 1. Fiecare bloc este format din unul sau mai multe pătrate alăturate, situate doar pe direcție orizontală. Blocurile sunt numerotate de la 1 la *n* și cad pe rând, în această ordine, întotdeauna de pe linia *L*, la intervale diferite de timp și au aceeași viteză de cădere. Fiecare pătrat din bloc cade până la linia cu cel mai mic număr de ordine care este neocupată de un alt pătrat al unui bloc căzut anterior. Dacă nu întâlnește un alt pătrat oprit anterior, atunci se oprește pe linia 1. Așadar, pătratele din același bloc pot să se oprească pe linii diferite.
!problema/patrate3?patrate3.png!
h2. Cerință
Determinați indicele coloanei de început [*c[~i~]*] și lungimea [*L[~max~]*] măsurată pe orizontală a zonei continue formată din pătrate cu proprietatea că fiecare coloană de pătrate a zonei are înălțimea cel puțin [*h*].
h2. Date de intrare
Fișierul de intrare $patrate3.in$ ...
Fișierul de intrare $patrate3.in$ conține:
* pe prima linie două numere naturale *n* și [*h*], separate printr-un spațiu, cu semnificația din enunț.
* fiecare din următoarele *n* linii conține câte două numere naturale *c* și *p*, separate printr-un spațiu. Valorile *c* și *p* de pe linia *i* + 1 reprezintă coloana corespunzătoare primului pătrat al capătului din stânga al blocului [*i*], respectiv numărul de pătrate din bloc.
h2. Date de ieșire
În fișierul de ieșire $patrate3.out$ ...
Fișierul de ieșire $patrate3.out$ conține pe o singură linie numerele naturale [*c[~i~]*] și [*L[~max~]*], separate printr-un spațiu. Dacă există mai multe soluții, atunci se afișează aceea pentru care [*c[~i~]*] este minim.
h2. Restricții
* $... ≤ ... ≤ ...$
* 1 ≤ *h* < *n* ≤ 1 000
* 2 ≤ *c* + *p* ≤ 1 000 000 000
* Problema admite soluție pentru toate datele de intrare.
h2. Exemplu
table(example).
|_. patrate3.in |_. patrate3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
table(example).
|_. patrate3.in |_. patrate3.out |_. Explicație |
| 4 2
3 2
2 6
7 3
6 3
| 6 3
| În figură, numerotarea pătratelor identifică blocurile din care acestea fac parte.
Zona de pătrate de lungime maximă incepe la coloana 6 și are lungimea 3.
|
== include(page="template/taskfooter" task_id="patrate3") ==
