Fişierul intrare/ieşire:betasah.in, betasah.outSursăOJI 2013, clasa a 9-a
AutorCarmen MincaAdăugată deMihai22eMihai Ionut Enache Mihai22e
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 xi yi, separate prin cate un spatiu, reprezentand pozitia damei i pe suprafata de joc (randul xi si coloana yi), pentru i=1,2,3,...,D;
  • pe linia D+1+j doua numere naturale nenule zj tj, separate printr-un singur spatiu, reprezentand pozitia patratului gri j pe suprafata de joc (randul xi si coloana yi), 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 ≤ yi ≤ xi ≤ N pentru i=1,2,3,...,D
  • 1 ≤ tj ≤ zj ≤ 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

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.
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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content