.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » acces

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
acces


Timp maxim de execuţie / test:
1.2s
Memorie totala disponibilă / stivă:
16MB / 16MB

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 ≤ 1000
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ă

Exemple

acces.inacces.outExplicaţii
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)

autor: Prof. Dan Pracsiu
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2011: sport2, macheta, butoane, mxl, segmente, tsunami, tort1, ec, ape, poligon4, stalpi2, furnici1, telecab, ikebana, posta, fotbal1, xmoto, radare, pamant, fagure, goe, papusa, taburet, joc17, mesaj3, zar1, joc16, talent, xy, arbore1, robot3, copii, hacker, terenuri3d, terenuri, expresie2, poteci, joc18
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, drumuri1, fillmat, secvb, siruri3, segmente, echilibru1, broscute, ksecv, paisprezece, proddiv, perechi2, expeval, maxtri, combcuv, dfs, qtri, blis, maxbin, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, matcnt, ssdj, dominant
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre fill: rebus, sarpe, insule, lacuri, zuzu, joc11, gradina, dreptunghiuri, drenaj, fillmat, parcela, tsunami, betasah, zona, zone, taxa, foto, ferma1, antitero, robotzi
surse trimise | ajutor