Pe o zonă în formă de dreptunghi cu laturile de lungimi N și M se găsesc NxM pătrate de latură 1. În centrul fiecărui pătrat se găsește înfipt câte un ac de grosime neglijabilă. Fiecare ac este descris de înălțimea sa. Această zonă se poate reprezenta ca un tablou bidimensional de dimensiuni N și M, iar fiecare element din matrice reprezintă înălțimea (număr natural nenul) fiecărui ac. În centrul pătratului (N,M) există o cameră de luat vederi de ultimă generație, mobilă, care se poate roti cu 3600 în orice plan, situată la nivelul solului. Dimensiunile camerei sunt neglijabile. De exemplu, dacă avem zona sub forma:
Din pătratul (4,4), în direcția N (nord), camera va obține Fig. 1, iar în direcția V (vest) va obține Fig. 2.
Pentru direcția N, camera va vedea acul de coordonatele (3,4) – în totalitate, iar acul (2,4) se va vedea doar parțial . Acul (1,4) nu se vede pentru că este acoperit total de (2,4). În direcția V, camera va vedea doar acul (4,3), deoarece (4,2) și (4,1) sunt acoperite total de (4,3). Pentru celelalte direcții se vor vedea parțial sau în totalitate acele (3,3), (3,2), (3,1), (2,3), (1,3), (2,2), (2,1), (1,2). Acul (1,1) nu se vede din cauza acului (2,2), care îl acoperă total. Acul (2,2) se vede doar parțial, pentru că o parte din el este acoperit de acul (3,3).
Cerința
1. Câte ace vede camera de luat vederi dacă se poate roti în plan vertical, doar în direcțiile N și V?
2. Câte ace vede camera de luat vederi dacă se poate roti în orice plan și în orice direcții?
Date de intrare
Fișierul de intrare ace.in conține pe prima linie numărul P care poate fi 1 sau 2, pentru prima, respectiv a doua cerință. Pe a doua linie se găsesc numerele N, M reprezentând dimensiunile tabloului, apoi pe următoarele N linii câte M numere naturale, despărțite prin câte un spațiu, reprezentând înălțimile acelor.
Date de ieșire
Fișierul de ieșire ace.out va conține pe prima linie numărul de ace văzute pentru cerință indicată de valoarea numărului P.
Restricții și precizări
2 ≤ N ≤ 10002 ≤ M ≤ 1000- Elementele matricei sunt numere naturale nenule mai mici decât
1000, cu excepția numărului de pe liniaNși coloanaMcare este0. - Pentru rezolvarea corectă a cerinței 1 se acordă 20 puncte, pentru rezolvarea corectă a cerinței 2 se acordă 70 de puncte, iar din oficiu se acordă 10 de puncte.
- Pentru cerința 2 există teste în valoare de 20 puncte cu
N,M ≤ 50. - Pentru cerința 2 există teste în valoare de 45 puncte cu
N,M ≤ 100.
Exemplul 1:
ace.in
1 4 4 8 5 4 7 2 7 4 6 5 5 3 2 6 6 3 0
ace.out
3
Explicație
Pentru cerința 1 avem direcțiile N și V: Pentru direcția N, camera va vedea acul de coordonatele (3,4) – în totalitate, iar acul (2,4) se va vedea doar parțial. Acul (1,4) nu se va vedea pentru că este acoperit total de (2,4). În direcția V, camera va vedea doar acul (4,3), deoarece acele (4,2) și (4,1) sunt acoperite total de acul (4,3).
Exemplul 2:
ace.in
2 4 4 8 5 4 7 2 7 4 6 5 5 3 2 6 6 3 0
ace.out
11
Explicație
Pentru cerința 2 camera va vedea cele trei ace din direcțiile N și V (vezi mai sus) și opt pentru celelalte direcții se vor vedea parțial sau în totalitate acele (3,3), (3,2), (3,1), (2,3), (1,3), (2,2), (2,1), (1,2). Acul (1,1) nu se vede din cauza celui de pe (2,2) care îl acoperă total. Acul (2,2) se vede doar parțial, pentru că o parte din el este acoperit de acul (3,3).
Exemplul 3:
ace.in
2 4 3 5 4 7 6 4 6 5 3 2 6 3 0
ace.out
8
Explicație
Pentru cerința 2 camera va vedea în N (3,3), (2,3), în V va vedea (4,2). În celelalte direcții camera va vedea parțial sau în totalitate acele (3,2), (3,1), (2,2), (1,2), (1,1).
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 ace:
//sursa problema ace - prof Tavi Dumitrascu
#include <bits/stdc++.h>
using namespace std;
int pp, N, M, i, j, x, y, l, c, h, hmax, p, q, nr, vede, pozl, pozc, min1;
int a[1005][1005], b[1005][1005];
int main()
{
freopen("ace.in", "r", stdin);
freopen("ace.out", "w", stdout);
scanf("%d\n", &pp);
scanf("%d%d\n", &N, &M );
min1=100004;
x = N;
y = M;
for ( i = 1; i<= N; i++)
for ( j =1; j<=M; j++)
scanf("%d",&a[i][j]);
vede = 0;
nr=0;
hmax = 0;
for (i = 1;i < x; i++)
if (nr == 0)
{
hmax = a[x-i][M];
b[x-i][M] = 2;
nr = 1;
pozl = i;
vede++;
}
else
{
if (a[x-i][M] * pozl > i * hmax)
{
pozl = i;
hmax = a[x - i][M];
b[x-i][M] = 2;
vede++;
}
}
nr=0;
hmax = 0;
for (i = 1;i < y; i++)
if (nr == 0)
{
hmax = a[N][y - i];
nr = 1;
pozl = i;
vede++;
}
else
{
if (a[N][y-i] * pozl > i * hmax)
{
pozl = i;
hmax = a[N][y - i];
vede++;
}
}
if (pp == 1){printf("%d\n",vede);return 0;}
for (l=1; l<x; l++)
for (c=1; c<y; c++)
{
h = 0;
p = x;
q = y;
nr = 0;
for (i = 1; i*l < x&& i*c <y ; i++)
{
if (b[p-i*l][q-i*c]==0)
{
b[p-i*l][q-i*c]=1;
if (nr==0)
{
hmax = a[p-i*l][q-i*c];
pozl = i;
vede++;
b[p-i*l][q-i*c]=2;
nr++;
}
else
if ((a[p-i*l][q-i*c]-h) * (pozl) > i * (hmax -h))
{
pozl = i;
hmax = a[p - i*l][q - i*c];
vede++;
b[p-i*l][q-i*c]=2;
}
}
}
}
printf("%d\n",vede);
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 
.
Rezolvarea problemei #2055 ace
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2055 ace 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!