Fișierul intrare/ieșire xy.in, xy.out Sursă ONI 2011 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 .

Xy (clasa a 6-a)

Una dintre pasiunile celor doi frați Rareș și Bogdan este de a inventa jocuri. Cel mai recent joc inventat de ei se numește xy și se joacă de către doi jucători ce completează pătrate alternativ pe o suprafață dreptunghiulară împărțită în nxm pătrate identice, ca în figurile alăturate. Se consideră că pătratul din colțul stânga-sus al suprafeței este poziționat pe linia 1 și coloana 1, iar pătratul din colțul dreapta-jos este poziționat pe linia n și coloana m.

Se consideră mutare, etapa în care unul dintre jucători completează cel puțin un pătrat de pe suprafața dreptunghiulară. Mutările se execută alternativ, astfel:

  • Primul jucător alege un pătrat, îl completează cu caracterul x și încearcă să traseze un X cât mai mare cu centrul în pătratul ales, ca în figura 3, în care pătratul ales este poziționat pe linia 3 și coloana 3.
  • Cel de-al doilea jucător alege și el un pătrat, îl completează cu caracterul y și încearcă să traseze un Y cât mai mare cu centrul în pătratul ales, ca în figura 4, în care pătratul ales este poziționat pe linia 3 și coloana 3.

Tabla de joc din figurile alăturate conține 6×5 pătrate poziționate pe 6 linii și 5 coloane. Cel mai mic X, respectiv cel mai mare, care poate fi trasat pe această tablă de joc este cel din figura 1, respectiv cel din figura 3, prin completarea cu caracterul x a pătratelor necompletate, putând fi trasat în orice loc corespunzător de pe tabla de joc.

Cel mai mic Y, respectiv cel mai mare, care poate fi trasat pe această tablă de joc prin completarea cu caracterul y a pătratelor necompletate, este cel din figura 2, respectiv cel din figura 4, putând fi trasat în orice loc corespunzător de pe tabla de joc.

Jocul se încheie dacă se ajunge într-una dintre următoarele situații:

  • unul dintre jucători alege ca centru un pătrat completat de oricare jucător la o mutare anterioară;
  • jucătorul ce trebuie să efectueze mutarea, completează pe tabla de joc doar pătratul ales ca centru și nu poate trasa X-ul sau Y-ul;
  • s-au efectuat toate mutările propuse.

Pentru că cei doi copii sunt frați, nu-i interesează cine câștigă.

Cerință

Scrieți un program care citește trei numere naturale n, m, k și un șir de k mutări pe care cei doi frați doresc să le efectueze, alternativ, în ordinea dată și apoi determină:

  • numărul maxim a de pătrate completate în timpului unei mutări;
  • numărul b de pătrate rămase libere după încheierea jocului;
  • numărul maxim c de pătrate completate care formează o suprafață dreptunghiulară pe tabla de joc la finalul jocului.

Date de intrare

Fișierul de intrare xy.in conține pe prima linie trei numere naturale n, m și k, separate prin câte un spațiu, cu semnificația din enunț. Următoarele k linii conțin fiecare câte două numere naturale i și j, separate prin câte un spațiu, reprezentând linia i și coloana j unde este poziționat pătratul ales drept centru pentru a se efectua mutarea propusă.

Date de ieșire

Fișierul de ieșire xy.out va conține pe prima linie cele trei numere determinate de program: a b c, separate prin câte un spațiu, în această ordine, cu semnificația din enunț.

Restricții

  • 0 < n, m, i, j < 101
  • 0 < i ≤ n
  • 0 < j ≤ m
  • 0 < k < 10000
  • n, m, i, j, k sunt numere naturale;
  • inițial, toate pătratele de pe tabla de joc sunt necompletate;
  • completarea unui pătrat se realizează prin scrierea caracterului x sau y în acesta, primul jucător completând doar cu caracterul x, iar al doilea jucător doar cu caracterul y;
  • fiecare jucător completează pe tablă mai întâi pătratul ales ca centru și apoi încearcă trasarea semnului său;
  • în timpul unei mutări, la trasarea unui X, respectiv Y, jucătorii pot utiliza pătrate completate într-o mutare anterioară, fără să le numere la această mutare;
  • o suprafață dreptunghiulară formată din pătrate completate de pe tabla de joc poate fi constituită din:
    • cel puțin un pătrat completat
    • mai multe pătrate completate situate pe o aceeași linie și coloane consecutive
    • mai multe pătrate completate situate pe o aceeași coloană și linii consecutive
    • mai multe pătrate completate situate pe linii și coloane consecutive

Exemplu

xy.in xy.out Explicații
6 5 5
3 2
4 4
3 4
2 4
5 4
5 17 9
La prima mutare, primul jucător trasează un X, cu centrul în linia 3 și coloana 2,
prin completarea a 5 pătrate cu caracterul x.
La a doua mutare, al doilea jucător trasează un Y cu centrul în linia 4 și coloana 4,
prin completarea a 4 pătrate cu caracterul y.
La a treia mutare, primul jucător trasează un X, cu centrul în linia 3 și coloana 4,
prin completarea doar a 3 pătrate cu caracterul x deoarece folosește 2 pătrate
completate la prima mutare.
La a patra mutare, al doilea jucător reușește să completeze cu caracterul y doar pătratul
ales ca centru, situat în linia 2 și coloana 4, și jocul se încheie deoarece nu se poate
realiza trasarea lui Y.
 

 
A cincea mutare propusă nu se efectuează întrucât jocul s-a încheiat.

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

Indicii de rezolvare

Arată 3 categorii