Fişierul intrare/ieşire:acces.in, acces.outSursăONI 2011 - clasa a 10-a
AutorDan PracsiuAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test0.325 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Acces

Considerăm o matrice cu L linii (numerotate de sus în jos de la 1 la L) şi C coloane (numerotate de la stânga la dreapta de la 1 la C) care memorează doar valori 0 şi 1. Mai mult, valorile egale cu 1 sunt grupate în mai multe dreptunghiuri pline, care nu se învecinează nici pe linii, nici pe coloane, nici pe diagonale. În exemplul din fig. 1 matricea este corectă deoarece cele 4 dreptunghiuri de 1 nu se învecinează. În schimb în fig. 2 există 2 dreptunghiuri de 1 învecinate pe coloană şi două învecinate pe diagonală, deci matricea este incorectă.

În această matrice se pot face deplasări doar pe direcţiile Vest şi Nord în elemente egale cu 0, deci din poziţia (i, j) se poate ajunge doar într-una dintre poziţiile (i, j-1) şi (i-1, j), marcate cu 0. În acest fel, pornind de la o anumită poziţie, prin deplasări succesive, pot fi accesate un anumit număr de elemente ale matricei egale cu 0. De exemplu, în fig. 1, din poziţia (2, 4) pot fi accesate 5 componente egale cu 0, iar din poziţia (5, 4) pot fi accesate 14 componente egale cu 0.
Trebuie să răspundeţi la Q întrebări, fiecare întrebare fiind de forma: “Câte din elementele egale cu zero ale matricei pot fi accesate din poziţia (i, j)?”

Cerinţă

Scrieţi un program care să determine, pentru fiecare întrebare, câte elemente egale cu 0 din matrice pot fi accesate din poziţia precizată în cadrul întrebării.

Date de intrare

Pe prima linie a fişierului acces.in se află două numere naturale L şi C separate printr-un spaţiu, reprezentând numărul liniilor, respectiv numărul coloanelor matricei. Pe următoarele L linii se găsesc câte C cifre binare, separate prin câte un spaţiu, reprezentând elementele matricei. Pe linia următoare se află numărul natural Q, reprezentând numărul întrebărilor. Pe următoarele Q linii se găsesc câte două numere naturale i şi j, separate prin câte un spaţiu, reprezentând poziţia corespunzătoare unei întrebări.

Date de ieşire

Fişierul acces.out conţine Q linii. Pe linia p (1 ≤ p ≤ Q) se află un număr natural kp reprezentând răspunsul la cea de-a p-a întrebare.

Restricţii

  • 4 ≤ L, C ≤ 1 000
  • 3 ≤ Q ≤ 500 000
  • Pentru orice întrebare i j se garantează că valoarea corespunzătoare din matrice este 0
  • Pentru toate testele, dreptunghiurile formate din valori de 1 nu se învecinează

Exemplu

acces.inacces.outExplicaţie
5 7
0 0 0 0 1 1 1
0 1 1 0 1 1 1
0 1 1 0 0 0 0
0 1 1 0 1 0 0
0 0 0 0 1 0 1
4
2 4
5 4
4 7
3 1
5
14
11
3
Pentru prima întrebare, cele 5 componente egale cu 0 care pot fi accesate sunt cele din
poziţiile (1, 1), (1, 2), (1, 3), (1, 4), (2, 4).
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content