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șiKși o foaie de matematică plină cuXși0. Determinați câte șiruri corecte deXși câte șiruri corecte de0se găsesc pe foaia dată. - Se dau
Qîntrebări de formaA B, în careAeste caracterulXsau0șiBeste 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ă exactBșiruri corecte deA. Foia se poate tăia înM -1variante: 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 = 1atunci pe a doua linie se găsesc în ordine numerele naturaleN,MșiK, separate prin câte un spațiu, apoi pe următoareleNlinii câteMcaractere de X sau 0 reprezentând foaia dată. - Dacă
P = 2atunci pe a doua linie se găsesc în ordine numerele naturaleN,MșiK, 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 = 1atunci fișierul de ieșirejocxzero.inconț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 = 2atunci fișierul de ieșirejocxzero.outconține peQlinii, câte un număr naturalPe o foaie dintr-un caiet de matematică de dimensiune
N x M(Nnumărul de linii șiMnumărul de coloane) sunt completate toate pătrățelele cuXsau0. Pentru un număr naturalKdat, numim șir corect, o secvență deKelemente consecutive pe linie, coloană sau diagonale care au aceeași valoare (Xsau0). 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=3conține6șiruri corecte deXși5șiruri corecte de0.Cerința
- Se dau numerele naturale
N,MșiKși o foaie de matematică plină cuXși0. Determinați câte șiruri corecte deXși câte șiruri corecte de0se găsesc pe foaia dată. - Se dau
Qîntrebări de formaA B, în careAeste caracterulXsau0șiBeste 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ă exactBșiruri corecte deA. Foia se poate tăia înM -1variante: 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.inconține pe prima linie un număr naturalPreprezentând cerința din problemă care trebuie rezolvată.- Dacă
P = 1atunci pe a doua linie se găsesc în ordine numerele naturaleN,MșiK, separate prin câte un spațiu, apoi pe următoareleNlinii câteMcaractere de X sau 0 reprezentând foaia dată. - Dacă
P = 2atunci pe a doua linie se găsesc în ordine numerele naturaleN,MșiK, 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 + 3se găsește numărul naturalQ. Pe următoareleQlinii se găsesc câte un caracterAși un număr naturalBdespărțite prin un spațiu.Date de ieșire
- Dacă
P = 1atunci fișierul de ieșirejocxzero.inconț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 = 2atunci fișierul de ieșirejocxzero.outconține peQlinii, 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 ≤ 1002 ≤ M ≤ 10 0001 ≤ K ≤ 1001 ≤ Q ≤ 100 0000 ≤ B ≤ 1 000 000 000- În fișierele de intrare caracterul
Xeste majusculă iar0este 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.in1 4 5 3 XXXX0 0XXX0 00X00 000XX
jocxzero.out6 5
Explicație
Pe prima linie sunt
2șiruri corecte deX, pe a doua un șir corect deX, pe diagonală avem2șiruri corecte deXși unul pe verticală.Pe ultima linie avem un șir corect de
0, pe prima coloana avem un șir corect de0, pe ultima coloană avem un șir corect de0, pe diagonală mai avem2șiruri corecte de0.Exemplu 2:
jocxzero.in2 4 5 3 XXXX0 0XXX0 00X00 000X0 2 0 1 X 1
jocxzero.out2 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 - Se dau numerele naturale
