Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | betasah.in, betasah.out | Sursă | OJI 2013, clasa a 9-a |
Autor | Carmen Minca | Adăugată de | |
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:
- numarul maxim M de patrate albe continute de un rand al suprafetei de joc;
- 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.in | betasah.out |
---|---|
This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...