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

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


Timp maxim de execuţie / test:
2s
Memorie totala disponibilă / stivă:
64MB / 8MB

Se dă o matrice de dimensiuni cu N linii şi M coloane. Toate elementele matricei au valoarea 0 sau 1. Vor exista Q întrebări de forma: există vreun dreptunghi cu L linii şi C coloane cu toate elementele egale cu 1 situat în întregime între liniile L1 şi L2 ale matricei, inclusiv L1 şi L2?

Cerinţă

Răspundeţi la cele Q întrebări afişând 1 dacă există cel puţin un dreptunghi care să satisfacă această condiţie şi 0 dacă nu există.

Date de intrare

Fişierul lcdr.in conţine pe prima linie numerele N M Q cu semnificaţia din enunţ. Următoarele N linii conţin fiecare câte M numere cu valoarea 0 sau 1, fără spaţii între ele. Urmează Q linii cu câte patru numere fiecare: L C L1 L2, cu semnificaţia din enunţ.

Date de ieşire

Fişierul lcdr.out va conţine Q numere, câte unul pe linie, reprezentând în ordine răspunsurile la întrebări.

Restricţii

• 1 ≤ N, M ≤ 500
• 1 ≤ Q ≤ 500 000

Exemple

lcdr.inlcdr.out
4 5 5 00000 11100 01111 01100 3 2 2 4 4 3 1 4 1 3 1 2 1 2 4 4 1 3 4 4 1 0 1 1 0

autor: Marius Dumitran
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la LOT SB 2011: cifre4, grad2, risipa, liste, pixy, domino2, neconex, testament, enigma, asfalt1, intervale, lant1, jocs, jb
De acelaşi autor: cuiburi, jb
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, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, 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 secvenţe: degrade, hora, simetric, egal, ruleta, ecran, sirag, pasi, firma, br, numere2, termen, div, teatru, repeat, ratb, 2sec, sport, pikachu, suma3, panouri, sir5, mare, hof, resturi, efort, xor1, livada1, diff, popic, guess, albine1, permutare, miere, atelier, obstacole, echilibru1, 3max, ksecv, maxbin, meteo1, galbeni, maxp, secvp, split, secvente2, ausoara, sminus, munte3, cool, betisoare, unudoi, charlie, lasere, arc, dominant, restaurare, roua
Despre sortare: harta, index, sort, concurs, baby, patrate2, repeat, turist, bacan, toys, scor2, chimie2, politics, submat, scoici, ham, jokes, trecere, multiplu, paralel, tvshow, sirag1, tabara, munte, sport, puncte1, sume1, schi, granita, tren3, sant1, volei1, poze, maroco, dreptc, dist1, tir1, control, mosia, popas, reactivi, siruri1, coach, anag, matrice4, sume2, urgenta, basm, vot, balcon, joc14, cerc, k1, segm, calorii, ordonare, greutati, arctir, macheta, poligon4, centrala, robot4, maxviz, sdmin, qtri, arme, flori1, parc1, mijloc, bile6, proiecte, patru, drept2, subsecvente, cursa1, eoliene, vintage, dreapta, riglef, rebus1, rascoala, zimeria, praslea, aperm, unudoi, gropi1, piscina, restaurare, cabana, culori3
Despre arbore de intervale: centrala, 3max, ripstick, ksecv1
surse trimise | ajutor