Pe o foaie dintr-un caiet de matematică de dimensiune N x M (N numărul de linii și M numărul de coloane) sunt completate toate pătrățelele cu X sau 0. Pentru un număr natural K dat, numim șir corect, o secvență de K elemente consecutive pe linie, coloană sau diagonale care au aceeași valoare (X sau 0). Două pătrățele de pe foaie sunt vecine pe aceeași diagonală dacă au un singur colț comun.

Exemplu din figura alăturată, pentru care N=4, M=5, K=3 conține 6 șiruri corecte de X și 5 șiruri corecte de 0.

Cerința

Se dau numerele naturale N, M și K și o foaie de matematică plină cu X și 0. Determinați câte șiruri corecte de X și câte șiruri corecte de 0 se găsesc pe foaia dată.
Se dau Q întrebări de forma A B, în care A este caracterul X sau 0 și B este un număr natural. Determinați în câte moduri putem tăia foaia de matematica vertical pentru a obține în subtabloul din partea stângă exact B șiruri corecte de A. Foia se poate tăia în M -1 variante: după prima coloană, a doua coloană, după a treia coloană, ș.a.m.d, până după penultima coloană.

Date de intrare

Fișierul de intrare jocxzero.in conține pe prima linie un număr natural P reprezentând cerința din problemă care trebuie rezolvată.

Dacă P = 1 atunci pe a doua linie se găsesc în ordine numerele naturale N, M și K, separate prin câte un spațiu, apoi pe următoarele N linii câte M caractere de X sau 0 reprezentând foaia dată.
Dacă P = 2 atunci pe a doua linie se găsesc în ordine numerele naturale N, M și K, separate prin câte un spațiu, apoi pe următoarele N linii câte M caractere de X sau 0 reprezentând foaia dată.

Pe linia N + 3 se găsește numărul natural Q . Pe următoarele Q linii se găsesc câte un caracter A și un număr natural B despărțite prin un spațiu.

Date de ieșire

Dacă P = 1 atunci fișierul de ieșire jocxzero.in conține pe o singură linie două numere naturale separate printr-un spațiu, reprezentând, în ordine, numărul de șiruri corecte de X și numărul de șiruri corecte de 0.

Dacă P = 2 atunci fișierul de ieșire jocxzero.out conține pe Q linii, câte un număr natural

Exemplu din figura alăturată, pentru care N=4, M=5, K=3 conține 6 șiruri corecte de X și 5 șiruri corecte de 0.

Cerința

Se dau numerele naturale N, M și K și o foaie de matematică plină cu X și 0. Determinați câte șiruri corecte de X și câte șiruri corecte de 0 se găsesc pe foaia dată.
Se dau Q întrebări de forma A B, în care A este caracterul X sau 0 și B este un număr natural. Determinați în câte moduri putem tăia foaia de matematica vertical pentru a obține în subtabloul din partea stângă exact B șiruri corecte de A. Foia se poate tăia în M -1 variante: după prima coloană, a doua coloană, după a treia coloană, ș.a.m.d, până după penultima coloană.

Date de intrare

Fișierul de intrare jocxzero.in conține pe prima linie un număr natural P reprezentând cerința din problemă care trebuie rezolvată.

Dacă P = 1 atunci pe a doua linie se găsesc în ordine numerele naturale N, M și K, separate prin câte un spațiu, apoi pe următoarele N linii câte M caractere de X sau 0 reprezentând foaia dată.
Dacă P = 2 atunci pe a doua linie se găsesc în ordine numerele naturale N, M și K, separate prin câte un spațiu, apoi pe următoarele N linii câte M caractere de X sau 0 reprezentând foaia dată.

Pe linia N + 3 se găsește numărul natural Q . Pe următoarele Q linii se găsesc câte un caracter A și un număr natural B despărțite prin un spațiu.

Date de ieșire

Dacă P = 1 atunci fișierul de ieșire jocxzero.in conține pe o singură linie două numere naturale separate printr-un spațiu, reprezentând, în ordine, numărul de șiruri corecte de X și numărul de șiruri corecte de 0.
Dacă P = 2 atunci fișierul de ieșire jocxzero.out conține pe Q linii, câte un număr natural
reprezentând răspunsul la întrebarea corespunzătoare din fișierul de intrare.

Restricții și precizări

1 ≤ N ≤ 100
2 ≤ M ≤ 10 000
1 ≤ K ≤ 100
1 ≤ Q ≤ 100 000
0 ≤ B ≤ 1 000 000 000
În fișierele de intrare caracterul X este majusculă iar 0 este caracterul cifra zero.
Pentru rezolvarea corectă a cerinței 1) se acordă 40 puncte, pentru rezolvarea corectă a cerinței 2) se
acordă 60 de puncte

Exemplu 1:

jocxzero.in

1
4 5 3
XXXX0
0XXX0
00X00
000XX

jocxzero.out

6 5

Explicație

Pe prima linie sunt 2 șiruri corecte de X, pe a doua un șir corect de X, pe diagonală avem 2 șiruri corecte de X și unul pe verticală.

Pe ultima linie avem un șir corect de 0, pe prima coloana avem un șir corect de 0, pe ultima coloană avem un șir corect de 0, pe diagonală mai avem 2 șiruri corecte de 0.

Exemplu 2:

jocxzero.in

2
4 5 3
XXXX0
0XXX0
00X00
000X0
2
0 1
X 1

jocxzero.out

2
0

Explicație

Putem tăia vertical după prima coloană, după a doua, după a treia și după a patra coloană. Dacă tăiem după prima și a doua obținem un singur șir corect de 0.

Indiferent pe unde tăiem nu putem avea un subtablou cu un singur șir corect de X.

#include <bits/stdc++.h>
using namespace std;

char s[10002],c;
bool a[102][10002];
int sus[102][10002], st[102][10002], sts[102][10002],stj[102][10002],b[4],sir[2][10002],d[2];
int i,j,N,M,K,Q,A,B,P,x,max1,p1,p2;

int cbinarp(int A,int B, int u)
{
    int i,j,k;
    if (B<sir[A][1]) return -1;
    if (B>sir[A][u]) return -1;
    if (B==sir[A][1]) return 1;
    i=1;
    j=u;
    while (i<=j)
    {
        k=(i+j)/2;
        if (sir[A][k]==B&&sir[A][k-1]<B) return k;
        else
            if (sir[A][k]>=B) j=k-1;
            else i=k+1;
    }
    return -1;
}

int cbinaru(int A,int B, int u)
{
    int i,j,k;
    if (B<sir[A][1]) return -1;
    if (B>sir[A][u]) return -1;
    if (B==sir[A][u]) return u;
    i=1;
    j=u;
    while (i<=j)
    {
        k=(i+j)/2;
        if (sir[A][k]==B&&(sir[A][k+1]>B||k==u)) return k;
        else
            if (sir[A][k]>B) j=k-1;
            else i=k+1;
    }
    return -1;
}

int main()
{
    freopen("jocxzero.in", "r", stdin);
    freopen("jocxzero.out", "w", stdout);
    scanf("%d\n",&P);
    scanf("%d %d %d\n", &N, &M, &K);
    for (j=1;j<=N;j++)
        {
            gets(s+1);
            for (i=1;i<=M;i++)
                if (s[i]=='X') a[j][i]=1;
                else
                if (s[i]=='0') a[j][i]=0;
        }
        st[1][1]=sus[1][1]=sts[1][1]=1;
        for (j=2;j<=M;j++)
        {
            if (a[1][j]==a[1][j-1]) st[1][j]=st[1][j-1]+1;
            else st[1][j]=1;
            sus[1][j]=1;
            sts[1][j]=1;
        }
        for (i=2;i<=N;i++)
        {
            if (a[i][1]==a[i-1][1]) sus[i][1]=sus[i-1][1]+1;
            else sus[i][1]=1;
            st[i][1]=1;
            sts[i][1]=1;
        }
        for (i=2;i<=N;i++)
            for (j=2;j<=M;j++)
                {
                    if (a[i][j]==a[i][j-1]) st[i][j]=st[i][j-1]+1;
                    else st[i][j]=1;
                    if (a[i][j]==a[i-1][j]) sus[i][j]=sus[i-1][j]+1;
                    else sus[i][j]=1;
                    if (a[i][j]==a[i-1][j-1]) sts[i][j]=sts[i-1][j-1]+1;
                    else sts[i][j]=1;
                }
        stj[N][1]=1;
        for (i=N-1;i>=1;i--)
            stj[i][1]=1;
        for (j=2;j<=M;j++)
            stj[N][j]=1;
        for (i=N-1;i>=1;i--)
            for (j=2;j<=M;j++)
                {
                    if (a[i][j]==a[i+1][j-1]) stj[i][j]=stj[i+1][j-1]+1;
                    else stj[i][j]=1;
                }
        for (i=1;i<=N;i++)
            for (j=1;j<=M;j++)
        {
            x=a[i][j];
            if (sus[i][j]>=K) b[x]++;
            if (st[i][j]>=K) b[x]++;
            if (sts[i][j]>=K) b[x]++;
            if (stj[i][j]>=K) b[x]++;
        }
    if (P==1)
        printf("%d %d\n", b[1], b[0]);
    else
    {
        for (j=1;j<=M;j++)
        {
            d[0]=0;
            d[1]=0;
            for (i=1;i<=N;i++)
            {
                if (st[i][j]>=K) d[a[i][j]]++;
                if (sus[i][j]>=K) d[a[i][j]]++;
                if (sts[i][j]>=K) d[a[i][j]]++;
                if (stj[i][j]>=K) d[a[i][j]]++;
            }
            sir[1][j]=sir[1][j-1]+d[1];
            sir[0][j]=sir[0][j-1]+d[0];
        }
        scanf("%d\n", &Q);
        for (i=1;i<=Q;i++)
        {
            scanf("%c %d\n",&c, &B);
            if (c=='X') A=1;
            else A=0;
            p1=cbinarp(A,B,M-1);
            p2=cbinaru(A,B,M-1);
            if (p1==-1) printf("0\n");
            else
                printf("%d\n",p2-p1+1);
        }
    }
    return 0;
}

Comentarii

Problema #2505 – jocxzero – Rezolvari PBInfo

Cerința

Date de intrare

Date de ieșire

Cerința

Date de intrare

Date de ieșire

Restricții și precizări

Exemplu 1:

Explicație

Exemplu 2:

Explicație

Mihai-Alexandru

Problema #2505 – jocxzero – Rezolvari PBInfo

Cerința

Date de intrare

Date de ieșire

Cerința

Date de intrare

Date de ieșire

Restricții și precizări

Exemplu 1:

Explicație

Exemplu 2:

Explicație

Problema #2501 – sum_cons_impare – Rezolvari PBInfo

Problema #251 – Interclasare2 – Rezolvari PBInfo

S-ar putea sa iti placa