!problema/betasah?fig1.jpg!
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).
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).
table.
| 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|
| !problema/betasah?tab1.jpg!
| !problema/betasah?tab2.jpg!
| !problema/betasah?tab3.jpg!
| !problema/betasah?tab4.jpg!
|
h2. 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.
h2. Date de intrare
Fișierul de intrare $betasah.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $betasah.out$ ...
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ț.
h2. 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;
h2. Exemplu
table(example).
|_. betasah.in |_. betasah.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|_. betasah.in |_. betasah.out |
| 6 3 4
3 2
5 2
5 4
3 1
4 3
6 4
1 1
|5
13
|
h3. 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.
!problema/betasah?tab5.jpg!
== include(page="template/taskfooter" task_id="betasah") ==
