Fișierul intrare/ieșire | patrate3.in, patrate3.out | Sursă | ONI 2009 clasa a 7-a |
---|---|---|---|
Autor | Emanuela Cerchez | Adăugată de | Razvan Dumitriu • dumitriu_razvan |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Patrate3 (clasa a 7-a)
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.
Cerință
Determinați indicele coloanei de început ci și lungimea Lmax 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.
Date de intrare
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.
Date de ieșire
Fișierul de ieșire patrate3.out conține pe o singură linie numerele naturale ci și Lmax, separate printr-un spațiu. Dacă există mai multe soluții, atunci se afișează aceea pentru care ci este minim.
Restricții
- 1 ≤ h < n ≤ 1 000
- 2 ≤ c + p ≤ 1 000 000 000
- Problema admite soluție pentru toate datele de intrare.
Exemplu
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. |