Fișierul intrare/ieșire tetris1.in, tetris1.out Sursă ONI 2013 clasa a 6-a
Autor Dana Lica Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 1 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Tetris1 (clasa a 6-a)

Gigel are instalat pe calculator un joc numit Tetris, în care pe o zonă dreptunghiulară cad succesiv piesele dintr-un șir de piese. Zona de joc este codificată sub forma unei table cu N linii și M coloane. Liniile le considerăm numerotate de la 1 la N de jos în sus, iar coloanele de la 1 la M și de la stânga la dreapta. Toate piesele sunt de forma unor pătrate. Ele intră în zona de joc începând cu linia N și cad către linia 1, deplasarea făcându-se pe verticală în cadrul acelorași coloane. Dacă în cădere întâlnește o piesă introdusă anterior în joc atunci ea se va opri exact deasupra ei.

O piesă intră în joc doar dacă poate fi introdusă complet pe zona delimitată de cele N linii și M coloane.

În desenul alăturat zona de joc are 7 linii și 8 coloane și în joc au intrat pe rând zece piese, numerotate de la 1 la 10, în ordinea introducerii lor pe tablă.

Un joc Tetris se termină când toate piesele din șir s-au așezat pe tablă sau când piesa care urmează nu poate fi introdusă în joc.

Cerință

Realizați un program care determină:
a) Numărul de ordine maxim al unei linii ocupată de o piesă;
b) Determinați numărul maxim de coloane alăturate ocupate de piese, în cadrul liniei determinate la punctul a).

Date de intrare

Fișierul de intrare tetris1.in conține pe prima linie două numere naturale N și M reprezentând numărul de linii, respectiv numărul de coloane ale zonei de joc. Următoarele linii conțin perechi de numere naturale, fiecare descriind câte o piesă în ordinea intrării ei în joc. Primul număr din pereche reprezintă lungimea laturii piesei, iar cel de al doilea reprezintă numărul de ordine al coloanei pe care se încearcă plasarea laturii stângi a piesei. Numerele de pe fiecare linie sunt separate printr-un singur spațiu.

Date de ieșire

În fișierul de ieșire tetris1.out se va scrie pe prima linie numărul maxim al liniei ocupate de o piesă, iar pe a doua linie numărul maxim de coloane alăturate ocupate de piese, din cadrul acestei linii.

Restricții

  • 1 ≤ toate numerele din fișierul de intrare ≤ 1000
  • Se asigură că pentru toate testele cel puțin prima piesă poate fi așezată pe tablă
  • Se asigură că numărul de ordine al coloanei pe care se încearcă plasarea laturii stângi a piesei este ≤ M
  • Fișierul de intrare conține cel mult 1.000.001 linii.
  • Se acordă 60% din punctajul unui test, dacă pe prima linie a fișierului de ieșire se află un singur număr și el reprezintă răspunsul corect la prima cerință. Dacă fișierul de ieșire conține două linii și pe a doua linie se află un singur număr ce reprezintă răspunsul corect la a doua cerință se obține 40% din punctajul testului.

Exemplu

tetris1.in tetris1.out Explicații
7 8
1 1
2 2
2 7
1 6
3 6
3 3
1 8
2 5
1 8
2 3
3 3
7
4
Exemplul din desen descrie ordinea în care au intrat piesele în joc. Linia 7 este linia cu număr
de ordine maxim ce este acoperită cu piese. Piesele 8 și 10 acoperă această linie, pe o secvență
de 4 coloane alăturate, iar piesa 9 acoperă doar o coloană, deci secvența maximă este de lungime 4.
Piesa 11 nu a mai putut fi introdusă în joc.

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

Indicii de rezolvare

Arată 4 categorii