Fişierul intrare/ieşire:	betasah.in, betasah.out	Sursă	OJI 2013, clasa a 9-a
Autor	Carmen Minca	Adăugată de	Mihai Ionut Enache •Mihai22e
Timp execuţie pe test	0.5 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Betasah

Jocul betasah se joaca folosindu-se doar piese asemanatoare damelor clasicului sah, numite tot dame. Suprafata de joc are o forma triunghiulara si este formata din N(N+1)/2 patrate identice dispuse pe N randuri si N coloane. Randurile se numeroteaza de sus in jos, de la 1 la N. Coloanele se numeroteaza de la stanga la dreapta, de la 1 la N. Primul rand contine un singur patrat, al doilea rand contine doua patrate alaturate, ..., al N-lea rand contine N patrate alaturate, ca in suprafetele de joc cu N=6 din figurile de mai jos. Din cele N(N+1)/2 patrate, K sunt gri, iar restul sunt albe. Pozitia fiecarui patrat de pe suprafata de joc este data de randul si coloana in care acesta este situat.

Pe suprafata de joc sunt asezate D dame in D patrate albe distincte, ocupandu-le. Intr-un patrat alb poate fi asezata o singura dama, iar intr-un patrat gri nu poate fi asezata nicio dama. Pozitia unei dame pe suprafata de joc este data de pozitia patratului alb in care este asezata dama.
Damele pot accesa orice patrat alb neocupat situat pe directiile: verticala, orizontala sau diagonala, numerotate de la 1 la 8 in figura b). Accesul pe o directie se face trecand din patrat alb in patrat alb (doar patrate albe neocupate) pana la intalnirea unui patrat gri sau a unui patrat alb ocupat de o alta dama sau pana la terminarea suprafetei de joc.
Numim patrat accesibil orice patrat alb neocupat (de pe suprafata de joc) care ar putea fi accesat de cel putin una din cele D dame.
De exemplu, pentru suprafata de joc din figura c) numarul de patrate accesibile (marcate cu X) de pe suprafata este 11; pentru suprafata de joc cu N=6, D=3 si K=4 din figura d) numarul de patrate accesibile de pe suprafata este 13. In figura e) sunt marcate cu X patratele accesibile fiecarei dame de pe suprafata de joc din figura d).

Cerinta

Scrieti un program care sa citeasca numerele naturale N D K, pozitiile damelor si ale patratelor gri pe suprafata de joc si care sa determine:

1. numarul maxim M de patrate albe continute de un rand al suprafetei de joc;
2. numarul P de patrate accesibile de pe suprafata de joc.

Date de intrare

Fisierul de intrare betasah.in contine:

• pe prima linie cele trei numere naturale N D K, separate prin cate un spatiu, cu semnificatia din enunt;

• pe linia i+1 doua numere naturale nenule x_i y_i, separate prin cate un spatiu, reprezentand pozitia damei i pe suprafata de joc (randul x_i si coloana y_i), pentru i=1,2,3,...,D;
  
• pe linia D+1+j doua numere naturale nenule z_j t_j, separate printr-un singur spatiu, reprezentand pozitia patratului gri j pe suprafata de joc (randul x_i si coloana y_i), pentru j=1,2,3,...,K.

Date de ieşire

Fisierul de iesire betasah.out va contine pe prima linie numarul natural M si pe a doua linie numarul natural P, cu semnificatia din enunt.

Restricţii

• 2 ≤ N ≤ 1000

• 1 ≤ D ≤ 100

• 1 ≤ K ≤ 50

• D + K ≤ N(N+1)/2

• 1 ≤ y_i ≤ x_i ≤ N pentru i=1,2,3,...,D

• 1 ≤ t_j ≤ z_j ≤ N pentru k=1,2,3,...,K

• numarul M se va scrie obligatoriu pe prima linie a fisierului de iesire betasah.in.

• numarul P se va scrie obligatoriu pe a doua linie a fisierului de iesire betasah.out.

• pentru rezolvarea corecta a cerintei 1) se acorda 20% din punctaj, iar pentru rezolvarea corecta a cerintei 2) se acorda 80% din punctaj.

Exemplu

Explicaţie

N=6, D=3, K=4.
Randurile 5 si 6 contin numarul maxim M=5 de patrate albe.
Numarul de patrate accesibile de pe suprafata de joc este P=13.
In desenul alaturat corespunzator suprafetei date, cele 13 patrate accesibile sunt marcate cu X.
Astfel, pe prima linie a fisierului betasah.out se va scrie numarul 5, iar pe a doua linie a fisierului se va scrie numarul 13.

Cum se trimit solutii?