Simulare ONI 2018 | jocxzero

Pe o foaie dintr-un caiet de matematică de dimensiune $N \times 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ță

1. 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ă.
2. 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.out 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 \leq N \leq 100$
• $2 \leq M \leq 10 \ 000$
• $1 \leq K \leq 100$
• $1 \leq Q \leq 100 \ 000$
• $0 \leq B \leq 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

Exemplul 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.

Exemplul 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.