Question

Cerința

În clasa a IX-a A sunt M elevi, numerotați de la 1 la M și fiecare are un număr preferat P. Plictisiți de ora de informatică, au inventat următorul joc:

pe o foaie de matematică desenează o tablă de joc de dimensiune N, formată din N linii și N coloane, numerotate de la 1la N; fiecare linie și fiecare coloană are câte N pătrățelefiecare elev alege un pătrățel și desenează un X centrat în pătrățelul ales, fiecare din cele 4laturi având cel mult P pătrățele desenate, fără a ieși de pe tabla de joc (să nu mâzgălească banca!!).icsurile desenate de elevi se pot suprapune.

În figura de mai jos este reprezentat un X desenat de elevul care alege pătrățelul de coordonate i j și preferă numărul 3.



Cunoscând dimensiunea N a tablei de joc, numărul M de elevi, coordonatele alese de fiecare elev și numărul preferat al fiecărui elev, determinați câte pătrățele de pe tablă rămân nedesenate.

Date de intrare

Programul citește de la tastatură numărul N M, iar apoi M tripletei j p, reprezentând coordonatele pătrățelului ales și numărul preferat de fiecare elev.

Date de ieșire

Programul va afișa pe ecran numărul de pătrățele nedesenate.

Restricții și precizări

1 ≤ N ≤ 10001 ≤ M ≤ 1000001 ≤ i,j ≤ N
0 ≤ p ≤ N/2

Exemplu

Intrare

10 5
1 2 1
6 6 3
7 3 2
2 5 2
9 8 3

Ieșire

62

Explicație

Exemplul corespunde tablei de joc de mai jos. Unele pătrățele au fost desenate de mai multe ori.


P.S.: Am atasat si poza pt explicație

Answer 1

Salut. O strategie simpla este sa creezi o matrice de 0 si sa aduni cu 1 patratele desenate. La sfarsit, numeri toate patratele care au ramas egale cu 0. Bineinteles, patratele unde sunt colorate de mai multe ori, vor avea valori chiar mai mari decat 1, dar asta nu conteaza. 
Uite aici codul. Am folosit un text numit tablou.txt pentru date, caci nu aveam chef sa le introduc de mana De asemenea o sa arate si matricea cum arata dupa colorare

#include <iostream>
#include <fstream>
using namespace std;

int a[10002][10002];
int main(){
int n,M,i0,j0,k,i,j,p,nr=0;
ifstream f("tablou.txt");
f>>n>>M;
//cin>>N>>M;
while(M>0){
//cin>>i0>>j0>>p;
f>>i0>>j0>>p;
a[i0][j0]++;
for(k=1;k<=p;k++){
if((i0-k)>0&&(j0-k)>0){
a[i0-k][j0-k]++;
}
if((i0-k)>0&&(j0+k)<n+1){
a[i0-k][j0+k]++;
}
if((i0+k)<n+1&&(j0-k)>0){
a[i0+k][j0-k]++;
}
if((i0+k)<n+1&&(j0+k)<n+1){
a[i0+k][j0+k]++;
}
}
M--;
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cout<<a[i][j]<<" ";
if(a[i][j]==0){
nr++;
}
}
cout<<endl;
}
cout<<"Nr patrate nedesenate:"<<nr;
return 0;
}