Rezolvare completă PbInfo #624 Sah1

Alex dorește să își învețe fratele să joace șah. După ce i-a explicat regulile, Alex vrea să vadă dacă fratele lui a înțeles, aşa că îi dă un mic test. Având o tablă de șah de N linii şi N coloane, Alex pune pe ea M ture (tura atacă doar pe coloana și linia pe care se află) și un rege. Apoi îi cere fratelui său să îi spună de câte ture este atacat regele în acel moment și pe câte căsuțe de pe tablă poate fi pus regele, astfel încât să nu se afle în șah.

În figura de mai jos avem trei ture şi un rege. Regele nu este atacat de nicio tură, fiindcă nu se află pe aceeaşi linie sau aceeaşi coloană cu niciuna dintre ele.

Cerința

Cunoscând dimensiunea N a tablei de șah, poziția regelui de pe tablă, numărul M de ture și poziția fiecărei ture de pe tablă, se cere:

a)să se afișeze numărul de ture care atacă regele în acel moment;
b)numărul de poziții în care regele poate fi pus, astfel încât să nu fie atacat de vreo tură.

Date de intrare

Fişierul de intrare sah1.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se află două numere naturale N și M, cu semnificația din enunț, pe linia a treia se află două numere naturale reprezentând poziția regelui pe tablă, iar pe fiecare dintre următoarele M linii se află câte două numere naturale reprezentând linia respectiv coloana unei ture.

Date de ieșire

Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință. În acest caz, în fişierul de ieşire sah1.out se va scrie un număr natural reprezentând numărul de ture ce atacă regele.

Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerință. În acest caz, în fișierul de ieșire sah1.out se va scrie pe prima linie un număr natural Q, reprezentând numărul de poziții pe care poate fi pus regele astfel încât să nu fie atacat de vreo tură.

Restricții și precizări

  • 2 ≤ N ≤ 10 000
  • 0 ≤ M ≤ min(2 000, N2-1)
  • Tabla de șah are liniile și coloanele numerotate de la 1 la N.
  • Regele poate fi pus pe orice căsuță de pe tablă care nu este ocupată de o tură sau care nu este atacată de vreo tură.
  • Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.

Exemplul 1:

sah1.in

1
4 3
3 1
1 2
2 3
4 3

sah1.out

0

Explicație

p = 1

Regele nu este atacat de nicio tură (vezi figura de mai sus).

Atenție! Pentru acest test se rezolvă doar cerința a).

Exemplul 2:

sah1.in

2
4 3
3 1
1 2
2 3
4 3

sah1.out

2

Explicație

p = 2

Singurele căsuțe ce nu sunt atacate de nicio tură sunt (3,1) și (3,4). (vezi figura de mai sus)

Atenție! Pentru acest test se rezolvă doar cerința b).

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Sah1:

#include <fstream>
#include<stdio.h>
using namespace std;
int c[10005],l[10005],n,m,p,i,j,nr=0,lr,cr,x,y,ni,nj;
int main()
{
    ifstream fin("sah1.in");
    fin>>p>>n>>m>>lr>>cr;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        l[x]=1;
        c[y]=1;
        if(x==lr||y==cr)
            nr++;
    }
    fin.close();
    ofstream fout("sah1.out");
    ni=nj=0;
    for(i=1;i<=n;i++){
        if(l[i]==0)
            ni++;
        if(c[i]==0)
            nj++;
    }


    if(p==1)
        fout<<nr<<'\n';
    else
        fout<<ni*nj<<'\n';
    fout.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #624 Sah1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #624 Sah1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!