Fişierul intrare/ieşire:patrate1.in, patrate1.outSursăONI 2009, clasa a 7-a
AutorSuzana GalatanAdăugată deandrici_cezarAndrici Cezar andrici_cezar
Timp execuţie pe test0.05 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Patrate1

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ţia 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.

După ce pătratele tuturor blocurilor au ajuns pe poziţiile finale, Ana trebuie să determine o zonă continuă de lungime maximă Lmax, măsurată pe orizontală, cu proprietatea că înălţimea fiecărei coloane a sa este cel puţin h.

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 patrate1.in conţine:

  • pe prima linie două număre 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 patrate1.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

patrate1.inpatrate1.out
4 2
3 2
2 6
7 3
6 3
6 3

Explicaţie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content