Suprafața plană a unei mese de pseudo-biliard este formată din n x n celule pătratice cu lungimea laturii egală cu 1 (o unitate), lipite, dispuse pe n linii numerotate de la 1 la n și n coloane, numerotate de la 1 la n. Pe masă se așează K bile, fiecare bilă găsindu-se în centrul unei anumite celule a mesei. Un jucător dorește să plaseze pe suprafața mesei un cadru pătratic având lungimea diagonalei egală cu D unități.

El trebuie să răspundă la m întrebări de forma: x y. Fiecare întrebare are semnificația: câte bile se găsesc în interiorul sau pe laturile cadrului ?

Cadrul se plasează astfel încât fiecare colț să fie poziționat în centrul unei celule, colțurile opuse să se găsească pe aceeași coloană, respectiv pe aceeași linie, iar colțul “de sus” să fie plasat în centrul celulei aflată pe linia x și coloana y.

Cerinţă

Cunoscând lungimea n a laturilor mesei, numărul m de întrebări, numărul K de bile așezate pe masă, pozițiile lor și lungimea D a diagonalei cadrului pătratic, se cere:
1. Numărul de celule care se vor găsi în întregime în interiorul cadrului, dacă acesta se așează pe suprafața mesei, conform descrierii de mai sus.
2. Câte un răspuns pentru fiecare dintre cele m întrebări.

Date de intrare

Fişierul de intrare pseudobil.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.
Pe linia a doua se găsesc numerele naturale n, K și D separate prin câte un spațiu.
Pe fiecare dintre următoarele K linii, se găsesc câte două numere a și b (a, b ≤ n) reprezentând linia și coloana celulei în centrul căreia va fi așezată o bilă.
Pe linia K + 3 se găsește un număr natural m.
Următoarele m linii conțin câte două numere naturale x și y, reprezentând linia și coloana celulei în centrul căreia se va plasa colțul “de sus” al cadrului.

Date de ieşire

Dacă valoarea lui p este 1, se va rezolva numai punctul 1 din cerință. În acest caz, în fişierul de ieşire pseudobil.out se va scrie un singur număr natural n1, reprezentând numărul de celule care se vor găsi în întregime în interiorul cadrului.
Dacă valoarea lui p este 2, se va rezolva numai punctul 2 din cerință. În acest caz, fişierul de ieşire pseudobil.out va conține m linii. Pe fiecare linie i se va scrie câte un număr natural n2, reprezentând răspunsul pentru întrebarea i.

Restricţii şi precizări

3 ≤ n ≤ 1500
1 ≤ K ≤ 55 000
2 ≤ D ≤ n – 1 , D – număr par
1 ≤ m ≤ 100 000
Pozițiile cadrului sunt distince.
Se garantează pentru x și y valori pentru care cadrul este plasat în interiorul suprafeței mesei de pseudo-biliard.
Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.
Pentru primele 35% dintre testele care verifică cerința 2, m ≤ 1000 și n ≤ 500
Pentru primele 75% din testele care verifică cerința 2, m ≤ 10000 și n ≤ 1000

pseudobil.in

pseudobil.out

pseudobil.in

pseudobil.out

3
2

Explicație

Pentru primul exemplu:

p = 1 n = 5, K = 2, D = 4 D = (3 unități + 2*0.5 unități) = 4

Numărul de celule aflate în întregime în interiorul cadrului este n1 = 5.

Atenție! Pentru acest test se rezolvă doar cerința 1.
Se observă că în acest caz este suficient să se citească datele aflate pe primele două linii.

Pentru al doilea exemplu:

p = 2, n = 6, K = 5, D = 4.
Prima întrebare este: 1 3 . Sunt două bile pe laturile cadrului și una în interior, deci n2 = 3
A doua întrebare este: 2 4. O bilă se găsește pe una dintre laturile cadrului și una în interior, deci n2 = 2

Atenție! Pentru acest test se rezolvă doar cerința 2.

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

/*  Solutie 100 puncte
    Complexitate: O(n * n + m  )
    prof. Constantin Galatan
*/
#include <fstream>
using namespace std;

ifstream fin("pseudobil.in");
ofstream fout("pseudobil.out");

typedef unsigned short M[2 * 1501][1501];
M su, sd, pu, pd;
M a, b;
unsigned sc[1501], ss[1501], s[1501];
int m, n, K, L, D, n1, n2, T;

inline void SumPart(M su, M sd, M a);

int main()
{
    fin >> T >> n >> K >> D;
    if ( T == 1 )  // rezolv numai cerinta a)
    {
        int nr = D - 1;
        n1 = nr;
        while ( true )
        {
            nr -=2;
            if ( nr < 0 ) break;
            n1 += 2 * nr;
        }
        fout << n1 << '\n';
    }
    else
    {
        int x, y;
        for ( int i = 0; i < K; ++i )
        {
            fin >> x >> y;
            b[n + y - x][y] = 1;
            a[x + y - 1][y] = 1;
            s[y]++;
        }

        for ( int j = 1; j <=  n; ++j )
            ss[j] = ss[j - 1] + s[j];
        L = D / 2 + 1;

        SumPart(su, sd, a);
        SumPart(pd, pu, b);
        int A, B, C, D, E, F;
        fin >> m;

        for ( int i = 0; i < m; ++i )
        {
            fin >> x >> y;

            A = ss[y - L]; B = K - ss[y + L - 1];
            if ( y > x + y - 2 )
                C = su[x + y - 2][y - 1];
            else
                C = su[x + y - 2][y];
            C -= su[x + y - 2][y - L];
            D = pu[n - x + y + 1][y + L - 1] - pu[n - x + y + 1][y];
            int X = x + 2 * (L - 1);
            if ( y > n - X + y  -  1)
                E = pd[n - X + y  -  1][y - 1];
            else
                E = pd[n - X + y  -  1][y];
            E -= pd[n - X + y   -1][y - L];
            F = sd[X + y   ][y + L - 1] - sd[X + y ][y];
            n2 = K - (A + B + C + D + E + F);

            fout << n2 << '\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}

void SumPart(M su, M sd, M a)
{
    int sp[1501];
    for ( int d = 1; d < 2 * n; ++d )
    {
        for (int j = 0; j <= n; ++j )
            sp[j] = 0;
        for ( int j = max(d - n + 1, 1); j <= min(d, n) ; ++j )
        {
            sp[j] = sp[j - 1] + a[d][j];
            su[d][j] = su[d - 1][j] + sp[j];
            if ( j >= d ) su[d][j] += su[d - 1][j - 1];
            sd[d][j] = ss[j] - su[d][j] + sp[j];
        }
    }
}

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 #1026 Pseudobil

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