Fişierul intrare/ieşire:betasah.in, betasah.outSursăOJI 2013, clasa a 9-a
AutorCarmen MincaAdăugată decocoClaudiu coco
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Betasah (clasa a 9-a)

Jocul betaşah se joacă folosindu-se doar piese asemănătoare damelor clasicului şah, numite tot dame. Suprafaţa de joc are o formă triunghiulară şi este formată din  pătrate identice dispuse pe N rânduri şi N coloane. Rândurile se numerotează de sus în jos, de la 1 la N. Coloanele se numerotează de la stânga la dreapta, de la 1 la N. Primul rând conţine un singur pătrat, al doilea rând conţine două pătrate alăturate,..., al N-lea rând conţine N pătrate alăturate, ca în suprafeţele de joc cu N=6 din figurile de mai jos. Din cele  pătrate, K sunt gri, iar restul sunt albe. Poziţia fiecărui pătrat de pe suprafaţa de joc este dată de rândul şi coloana în care acesta este situat.

Pe suprafaţa de joc sunt aşezate D dame în D pătrate albe distincte, ocupându-le. Într-un pătrat alb poate fi aşezată o singură damă, iar într-un pătrat gri nu poate fi aşezată nicio damă. Poziţia unei dame pe suprafaţa de joc este dată de poziţia pătratului alb în care este aşezată dama.
Damele pot accesa orice pătrat alb neocupat situat pe direcţiile: verticală, orizontală sau diagonală, numerotate de la 1 la 8 în figura b). Accesul pe o direcţie se face trecând din pătrat alb în pătrat alb (doar pătrate albe neocupate) până la întâlnirea unui pătrat gri sau a unui pătrat alb ocupat de o altă damă sau până la terminarea suprafeţei de joc.
Numim pătrat accesibil orice pătrat alb neocupat (de pe suprafaţa de joc) care ar putea fi accesat de cel puţin una din cele D dame.
De exemplu, pentru suprafaţa de joc din figura c) numărul de pătrate accesibile (marcate cu X) de pe suprafaţă este 11; pentru suprafaţa de joc cu N=6, D=3 şi K=4 din figura d) numărul de pătrate accesibile de pe suprafaţă este 13. În figura e) sunt marcate cu X pătratele accesibile fiecărei dame de pe suprafaţa de joc din figura d).

Patrate accesibile damei din randul 3 si coloana 2Pătratele accesibile damei din rândul 5 şi coloana 2Pătratele accesibile damei din rândul 5 şi coloana 4Pătratele accesibile de pe suprafaţa de joc

Cerinte

Scrieţi un program care să citească numerele naturale N, D, K, poziţiile damelor şi ale pătratelor gri pe suprafaţa de joc şi care să determine:
a) numărul maxim M de pătrate albe conţinute de un rând al suprafeţei de joc;
b) numărul P de pătrate accesibile de pe suprafaţa de joc.

Date de intrare

Fişierul de intrare betasah.in conţine:
- pe prima linie cele trei numere naturale N, D şi K, separate prin câte un spaţiu, cu semnificaţia din enunţ;
- pe linia i+1 două numere naturale nenule xi şi yi, separate printr-un singur spaţiu, reprezentând poziţia damei i pe suprafaţa de joc (rândul xi şi coloana yi), pentru i=1,2,3,…,D;
- pe linia D+1+j două numere naturale nenule zj şi tj, separate printr-un singur spaţiu, reprezentând poziţia pătratului gri j pe suprafaţa de joc (rândul zj şi coloana tj), pentru j=1,2,3,…,K.

Date de ieşire

Fişierul de ieşire betasah.out va conţine pe prima linie numărul natural M şi pe a doua linie numărul natural P, cu semnificaţia din enunţ.

Restricţii

• 2 ≤ N ≤ 1000;
• 1 ≤ D ≤ 100;
• 1 ≤ K ≤ 50; 
• D + K ≤ ;
• 1 ≤ yi ≤ xi ≤ N pentru i=1,2,3,...,D;
• 1 ≤ tj ≤ zj ≤ N pentru j=1,2,3,...,K;
• numărul M se va scrie obligatoriu pe prima linie a fişierului de ieşire betasah.out;
• numărul P se va scrie obligatoriu pe a doua linie a fişierului de ieşire betasah.out;

Exemplu

betasah.inbetasah.out
6 3 4
3 2
5 2
5 4
3 1
4 3
6 4
1 1
5
13

Explicaţie

N=6, D=3, K=4.
Rândurile 5 şi 6 conţin numărul maxim M=5 de pătrate albe.
Numărul de pătrate accesibile de pe suprafaţa de joc este P=13.

În desenul alăturat corespunzător suprafeţei date, cele 13 pătrate accesibile sunt marcate cu X.
Astfel, pe prima linie a fişierului betasah.out se va scrie numărul 5, iar pe a doua linie a fişierului se va scrie numărul 13.

Trebuie sa te autentifici pentru a trimite solutii. Click aici