Fișierul intrare/ieșire betasah.in, betasah.out Sursă OJI 2013, clasa a 9-a
Autor Carmen Mincă Adăugată de avatar coco Claudiu coco
Timp de execuție pe test 0.1 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

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 2 Pătratele accesibile damei din rândul 5 și coloana 2 Pătratele accesibile damei din rândul 5 și coloana 4 Pă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.in betasah.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii