Fișierul intrare/ieșire tetris.in, tetris.out Sursă ONI 2009 clasa a 6-a
Autor Cristina Sichim Adăugată de avatar francu Cristian Frâncu francu
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 fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Tetris (clasa a 6-a)

La începutul lunii aprilie a fost lansată o nouă versiune a cunoscutului joc TETRIS. Un pasionat jucător, Nicușor, este nerăbdător să joace acest joc și de aceea citește cu atenție regulamentul:

  • jocul se desfășoară pe o suprafață dreptunghiulară, împărțită în m x n pătrate identice cu latura de 1cm, dispuse pe m linii și n coloane;
  • jucătorul are la dispoziție s piese, fiecare piesă fiind un pătrat de latură 1cm pe care este înscris un număr natural nenul mai mic sau egal cu 9, reprezentând valoarea piesei;
  • inițial, toate cele s piese sunt așezate într-un șir, în afara suprafeței de joc;
  • numim turn un șir de piese așezate în aceeași coloană, una deasupra celeilalte, ultima piesă așezată în coloană fiind vârful turnului; înălțimea unui turn reprezintă numărul de piese ce alcătuiesc turnul;
  • jocul începe cu așezarea primei piese din șir pe suprafața de joc în pătratul din colțul-stânga jos;
  • în continuare, se încearcă așezarea celorlalte piese, în ordinea în care acestea apar în șir, după următoarele reguli:
    • se caută, pe suprafața de joc, de la stânga la dreapta, primul turn de înălțime strict mai mică decât m care conține în vârf cele mai multe piese cu aceeași valoare ca a piesei ce trebuie adăugate;
    • dacă există un astfel de turn, piesa va fi plasată în vârful său;
    • dacă nu există un astfel de turn, se caută, pe suprafața de joc, de la stânga la dreapta, primul turn ce conține cele mai puține piese. Piesa se așează în vârful acestui turn numai dacă numărul de piese ce formează turnul este strict mai mic decât m;
  • dacă, imediat după adăugarea unei piese se obține un turn care la vârf conține 3 piese cu aceeași valoare, atunci toate cele 3 piese sunt eliminate de pe suprafața de joc;
  • jocul se încheie atunci când pe suprafața de joc nu mai sunt locuri libere sau când se termină șirul de piese.

Exemplu. Dacă suprafața are configurația din fig.1 și trebuie adăugată piesa cu valoarea 6, atunci aceasta va fi așezată în vârful turnului al treilea, deasupra piesei cu numărul 9, obținându-se configurația din fig.2; iar dacă valoarea piesei ce trebuie așezată este 1 atunci aceasta se așează deasupra primului turn ce conține în vârf două valori 1 (fig.3), după care cele 3 piese cu valoarea 1 se elimină de pe suprafața de joc (fig.4);

Cerință

Scrieți un program care să determine, pentru o anumită suprafață de joc și un șir de piese dat, numărul p de piese așezate pe suprafața de joc, numărul t de piese aflate pe suprafață la încheierea jocului, numărul h de piese din cel mai înalt turn aflat pe suprafața de joc în timpul jocului.

Date de intrare

Fișierul de intrare tetris.in conține pe prima linie cele trei numere naturale m n s separate prin câte un spațiu.
Pe următoarea linie se află șirul celor s cifre nenule separate prin câte un spațiu, reprezentând valorile celor s piese, în ordinea în care vor fi adăugate pe suprafața de joc.

Date de ieșire

Fișierul de ieșire tetris.out conține pe prima linie numărul p, pe a doua linie numărul t și pe a treia linie numărul h.

Restricții

  • 1 ≤ m ≤ 1000
  • 1 ≤ n ≤ 9
  • 1 ≤ s ≤ 100000
  • Nu se așează pe suprafață mai multe piese în același moment.

Exemplu

tetris.in tetris.out Explicație
4 2 8
1 2 2 1 2 4 5 4
8
5
3
Adăugarea pieselor modifică suprafața de joc astfel:
 

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

Indicii de rezolvare

Arată 4 categorii