Pe o tablă de şah cu N linii şi N coloane sunt plasaţi M nebuni. După cum se ştie de la jocul de şah, nebunii atacă doar în diagonală.

O poziţie de pe tabla de şah este considerată sigură dacă nu este atacată de niciun nebun aflat pe tablă.

Cerinţă

Scrieţi un program care să determine numărul de poziţii sigure de pe tabla de şah.

Date de intrare

Fișierul de intrare nebuni.in conține pe prima linie numerele naturale N M, separate prin spaţiu, cu semnificaţia din enunţ. Pe următoarele M linii sunt descrise poziţiile (linia şi coloana, separate prin spaţiu) celor M nebuni, câte un nebun pe o linie a fişierului.

Date de ieșire

Fișierul de ieșire nebuni.out va conține o singură linie pe care va fi scris un număr natural reprezentând numărul de poziţii sigure de pe tabla de şah.

Restricții și precizări

1 ≤ N ≤ 1 000 000
1 ≤ M < 16 500
Liniile şi coloanele sunt numerotate de la 1 la N.
Pentru 50% dintre teste N ≤ 300.
Pentru 60% dintre teste M ≤ 1000.

Exemplu

nebuni.in

nebuni.out

Explicație

Pe tabla de şah de dimensiune 5x5 se află 4 nebuni.
Poziţiile atacate de cei 4 nebuni sunt marcate cu gri.

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 Nebuni:

//Emanuela Cerchez, 100 puncte
#include <fstream>
#define NMAX 1000001
#define MMAX 100001

using namespace std;

int N, M;
int X[MMAX], Y[MMAX];
int DP[2*NMAX], DS[2*NMAX];
int nrs[2*NMAX];
long long int Rez;

void citire();
void afisare();
void rezolvare();

int main()
{
citire();
rezolvare();
afisare();
return 0;
}


void afisare()
{ofstream fout("nebuni.out");
 fout<<Rez<<'\n';
 fout.close();
}

void citire()
{ifstream fin("nebuni.in");
 int i;
 fin >> N >> M;
 for (i=1; i<=M; i++)
     fin>>X[i]>>Y[i];
}
 
int nrcelule(int i)
{
if (i <= N) return i;
return 2*N-i;
}


void rezolvare()
{int i, Sf, Inc, LInceput, CInceput, LSfarsit, CSfarsit, SI, SDS, SDP;
for (i=1; i<=M; i++)
    {DP[X[i] - Y[i] + N]=1;
     DS[X[i] + Y[i] - 1]=1;};
SDP=SDS=0;
for (i=1; i<2*N; i++)
    {if (DP[i]) SDP+=nrcelule(i);
     if (DS[i]) SDS+=nrcelule(i);}

nrs[1]=DS[1]==1;
for (i=2; i<2*N; i++) nrs[i]=nrs[i-2]+(DS[i]==1);

SI=0;    
for (i=1; i<2*N; i++)
    if (DP[i]) 
    {if (i<=N) {LInceput=1; CInceput = N-i+1; LSfarsit=i; CSfarsit=N;}
        else {LInceput=i-N+1; CInceput = 1; LSfarsit=N; CSfarsit =2*N-i;}
    Sf=LSfarsit+CSfarsit-1;
    Inc=LInceput+CInceput-1;
    SI+=nrs[Sf]-nrs[Inc-2];
    }   

Rez=(long long int)N*N - (SDP+SDS-SI);
}

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 #1226 Nebuni

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1226 Nebuni 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!

Rezolvare completă PbInfo #1226 Nebuni