Fișierul intrare/ieșire patrate3.in, patrate3.out Sursă ONI 2009 clasa a 7-a
Autor Emanuela Cerchez Adăugată de avatar dumitriu_razvan Razvan Dumitriu dumitriu_razvan
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 6 categorii