Simulare ONI 2018 | jocxzero

This was the problem page during the contest. Access the current page here.
Time limit: 0.2s Memory limit: 64MB Input: jocxzero.in Output: jocxzero.out

Pe o foaie dintr-un caiet de matematică de dimensiune N×MN \times M (NN numărul de linii și MM numărul de coloane) sunt completate toate pătrățelele cu X sau 0. Pentru un număr natural KK dat, numim șir corect, o secvență de KK 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=4N = 4, M=5M = 5, K=3K = 3 conține 66 șiruri corecte de X și 55 șiruri corecte de 0.

Cerință

  1. Se dau numerele naturale NN, MM și KK ș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 QQ întrebări de forma A,BA, B, în care AA este caracterul X sau 0 și BB 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 BB șiruri corecte de AA. Foia se poate tăia în M1M - 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 PP reprezentând cerința din problemă care trebuie rezolvată.

Dacă P=1P = 1 atunci pe a doua linie se găsesc în ordine numerele naturale N,MN, M și KK, separate prin câte un spațiu, apoi pe următoarele NN linii câte MM caractere de X sau 0 reprezentând foaia dată.
Dacă P=2P = 2 atunci pe a doua linie se găsesc în ordine numerele naturale N,MN, M și KK, separate prin câte un spațiu, apoi pe următoarele NN linii câte MM caractere de X sau 0 reprezentând foaia dată.
Pe linia N+3N + 3 se găsește numărul natural QQ. Pe următoarele QQ linii se găsesc câte un caracter AA și un număr natural BB despărțite prin un spațiu.

Date de ieșire

Dacă P=1P = 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=2P = 2 atunci fișierul de ieșire jocxzero.out conține pe QQ 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

  • 1N1001 \leq N \leq 100
  • 2M10 0002 \leq M \leq 10 \ 000
  • 1K1001 \leq K \leq 100
  • 1Q100 0001 \leq Q \leq 100 \ 000
  • 0B1 000 000 0000 \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)1) se acordă 4040 puncte, pentru rezolvarea corectă a cerinței 2)2) se acordă 6060 de puncte

Exemplul 1

jocxzero.in

1
4 5 3
XXXX0
0XXX0
00X00
000XX

jocxzero.out

6 5

Explicație

Pe prima linie sunt 22 șiruri corecte de X, pe a doua un șir corect de X, pe diagonală avem 22 ș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 22 ș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.

Log in or sign up to be able to send submissions!