Enunț

Păcală a reușit să ducă la bun sfârșit înțelegerea cu boierul căruia-i fusese slugă și, conform învoielii, boierul trebuie să-l răsplătească dându-i o parte din livada sa cu pomi fructiferi. Boierul este un om foarte ordonat, așa că livada sa este un pătrat cu latura de N metri unde, pe vremuri, fuseseră plantate N rânduri cu câte N pomi fiecare. Orice pom fructifer putea fi identificat cunoscând numărul rândului pe care se află și poziția sa în cadrul rândului respectiv. Cu timpul, unii pomi s-au uscat şi acum mai sunt doar P pomi. Păcală trebuie să-și delimiteze în livadă o grădină pătrată cu latura de K metri.

Cerința

Cunoscând dimensiunile livezii și grădinii, numărul pomilor din livadă și poziția fiecăruia, determinați numărul maxim de pomi dintr-o grădină pătrată de latură K și numărul modurilor în care poate fi amplasată grădina cu numărul maxim de pomi.

Date de intrare

Fișierul gradina.in conține:

pe prima linie numerele naturale N, P și K, separate prin câte un spațiu, cu semnificaţia din enunţ;
pe următoarele P linii câte 2 numere naturale Lin și Col, separate printr-un spațiu, reprezentând numărul rândului, respectiv poziția în rând a fiecărui pom din livadă.

Date de ieșire

Fișierul gradina.out va conține:

pe prima linie numărul maxim de pomi fructiferi dintr-o grădină pătrată cu latura de K metri;
pe a doua linie numărul de posibilități de a amplasa grădina astfel încât să conțină numărul maxim de pomi determinat.

Restricții și precizări

2 ≤ N ≤ 1000
1 ≤ P ≤ N*N
1 ≤ K ≤ N

Exemplu

gradina.in

gradina.out

5
5

Explicație

Grădina lui Păcală poate avea maximum 5 pomi fructiferi. Ea poate fi amplasată în 5 moduri, având colțul stânga-sus de coordonate: (5, 3), (5, 4), (5, 5), (6, 6), (7, 3).

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

# include <fstream>
# include <cstdio>
# define DIM 1003
using namespace std;
int n, p, k, a[DIM][DIM], pmax, nsol;

void read ()
{
    FILE *fin=fopen("gradina.in","rt");
    fscanf(fin,"%d%d%d",&n,&p,&k);
    for(int i=1;i<=p;++i)
    {
        int x, y;
        fscanf(fin,"%d%d",&x,&y);
        a[x][y]=1;
    }
    fclose(fin);
}

void solve ()
{
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
    for(int i=k;i<=n;++i)
        for(int j=k;j<=n;++j)
        {
            int np = a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k];
            if (np>pmax)
            {
                pmax=np;
                nsol=1;
            }
            else if (np==pmax)
                ++nsol;
        }
}

int main ()
{
    read ();
    solve ();

    FILE *fout = fopen("gradina.out","wt");
    fprintf(fout,"%d\n%d\n",pmax,nsol);
    fclose(fout);
    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 #1515 gradina

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