Se dă o matrice cu numere naturale nenule, pătratică, cu liniile şi coloanele numerotate de la 1 la N. Fiecare număr din matrice reprezintă înălţimea unui pilon plasat în acea poziţie.

Putem plasa un observator „sub” matrice (adică pe o poziţie i j cu i>N şi 1<=j<=N), de unde poate vedea în 3 direcţii:

nord (pe coloana j);
nord-vest (elemente din matrice de pe poziţii is,js cu i-is =j-js, dacă există astfel de elemente);
nord-est (elemente din matrice de pe poziţii is,js cu i-is =js-j, dacă există astfel de elemente);

Plasat într-o poziţie şi privind pe una dintre direcţii, observatorul poate vedea doar pilonii pe care nu îi separă de observator niciun pilon cu înălţimea mai mare şi nici egală. În exemplul alăturat avem o matrice cu 5 linii şi 5 coloane. Observatorul de pe poziţia (6,1) va vedea pe direcţia nord doar pilonii de înălţimi 1, 2 şi 5 (celulele haşurate), iar în direcţia nord-est, doar pilonul cu înălţimea 7.

Observatorul de pe poziţia (8,1) va vedea pe direcţia nord de asemenea pilonii de înălţimi 1, 2 şi 5, iar în direcţia nord-est, pilonii de înălţimi 1 şi 4.

Cerinţa

Se cunoaşte configuraţia matricei şi mai multe poziţii posibile ale observatorului. Să se determine, pentru fiecare poziţie, numărul de piloni pe care îi vede observatorul plasat acolo.

Date de intrare

Fişierul matrice1.in are pe prima linie un număr natural N, dimensiunea matricei. Pe fiecare din următoarele N linii se găsesc câte N numere naturale. Numerele de pe aceeaşi linie se separă prin câte un spaţiu.

Pe linia următoare se găseşte un număr Q care reprezintă numărul de poziţii ale observatorului. Pe fiecare dintre următoarele Q linii sunt câte 2 numere naturale, separate printr-un un spaţiu, reprezentând o poziţie a observatorului (mai întâi linia, apoi coloana).

Date de ieşire

Fişierul matrice1.out va avea Q linii. Pe fiecare linie se găseşte numărul de piloni văzuţi de observator din fiecare poziţie a sa, în ordinea dată în fişierul de intrare.

Restricţii

2<=N<=500;
1<=Q<=500000;
Elementele matricei sunt numere naturale cuprinse între 1 şi 30000 (inclusiv)
Pentru fiecare poziţie i,j a observatorului avem N+1 <=i<=2*N şi 1<=j<=N;

Exemplu

matrice1.in

matrice1.out

4
5
7

Explicaţie

Pentru prima poziţie, 6, 1 observatorul vede 3 piloni în direcţia nord şi un pilon în direcţia nord-est, în total 4.

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

#include <fstream>
#define DIM 1010
using namespace std;

int a[DIM][DIM];
int n, Q, i, j, maxim, lin, col, c, sum;
int N[DIM], E[DIM], V[DIM];

int main() {
    ifstream fin("matrice1.in");
    ofstream fout("matrice1.out");
    fin>>n;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            fin>>a[i][j];

    for (j=1;j<=n;j++) {
        maxim = 0;
        for (i=n;i>=1;i--)
            if (a[i][j] > maxim) {
                N[j]++;
                maxim = a[i][j];
            }
    }
    //vest
    for (c=1;c<=n;c++) {
        i = n;
        j = c;
        maxim = 0;
        while (i>=1 && j>=1) {
            if (a[i][j] > maxim) {
                maxim = a[i][j];
                V[c]++;
            }
            i--;j--;
        }
    }

    for (c=1;c<=n;c++) {
        i = n;
        j = c;
        maxim = 0;
        while (i>=1 && j<=n) {
            if (a[i][j] > maxim) {
                maxim = a[i][j];
                E[c]++;
            }
            i--;j++;
        }
    }

    fin>>Q;
    while (Q) {
        fin>>i>>j;
        sum = N[j];
        lin = n;
        col = j - (i-lin);
        if (col >= 1)
            sum += V[col];
        col = j+(i-lin);
        if (col <=n)
            sum += E[col];
        fout<<sum<<"
";
        Q--;
    }

    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 #148 matrice1

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