Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | elicop.in, elicop.out | Sursă | OJI 2012 - clasa a 9-a |
| Autor | Doru Popescu Anastasiu | Adăugată de |  Simoiu Robert •SpiderMan |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 6144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Elicop
Un teren de fotbal este folosit pentru aterizarea elicopterelor. Gazonul de pe stadion este parcelat în pătrăţele de aceeaşi dimensiune, cu laturile paralele cu marginile terenului. Liniile cu pătrăţele de gazon sunt numerotate de sus în jos cu numerele 1, 2, ..., m, iar coloanele cu pătrăţele de gazon sunt numerotate de la stânga la dreapta cu numerele 1, 2, ..., n. Din cauza tipului diferit de iarbă se ştie care dintre pătrăţele de gazon sunt afectate sau nu de umbră. Acest lucru este precizat printr-un tablou bidimensional a cu m linii şi n coloane, cu elemente 0 şi 1 (aij = 0 înseamnă că pătrăţelul aflat pe linia i şi coloana j este afectat de umbră, iar aij = 1 înseamnă că pătrăţelul aflat pe linia i şi coloana j nu este afectat de umbră). Fiecare elicopter are 3 roţi pe care se sprijină. Roţile fiecărui elicopter determină un triunghi dreptunghic isoscel. Elicopterele aterizează, astfel încât triunghiurile formate să fie cu catetele paralele cu marginile terenului. În exemplul următor avem patru elicoptere.
Pentru a preciza poziţia unui elicopter pe teren este suficient să cunoaştem linia şi coloana vărfurilor ipotenuzei şi poziţia vârfului deasupra (codificată prin 1) sau dedesubtul ipotenuzei (codificată prin -1). Pentru exemplu, elicopterul din stânga sus este dat prin (1, 1), (3, 3) şi -1, cel din dreapta sus prin (1, 9), (5, 5) şi 1, cel din stânga jos prin (5, 1), (6, 2) şi 1, iar cel din dreapta jos prin (5, 9), (6, 8) şi 1.
Un elicopter se consideră că a aterizat greşit, dacă triunghiul format sub el (definit mai sus) are mai mult de jumătate din pătrăţele afectate de umbră.
Administratorul terenului de fotbal doreşte să determine numărul N1 de elicoptere, care nu afectează nici un pătrăţel din teren şi numerele de ordine al elicopterelor, care au aterizat greşit în ordine crescătoare: e1, e2, ..., eN2, ştiind că există k elicoptere codificate prin numerele 1, 2, ..., k.
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.in | acces.out | Explicaţ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). |
