Fişierul intrare/ieşire:	ozn.in, ozn.out	Sursă	Baraj Shumen juniori 2014 - etapa 2
Autor	Cristian Francu	Adăugată de	Catalin Francu •Catalin.Francu
Timp execuţie pe test	0.4 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	3/5

Vezi solutiile trimise

OZN (clasele 8-9)

Bucureştiul este asediat de OZN-uri! Harta Bucureştiului are formă dreptunghiulară şi este formată din M x N clădiri cu latura de o unitate. Se cunoaşte înălţimea fiecărei clădiri. OZN-urile au formă pătrată şi sunt caracterizate prin următoarele valori:

• dimensiunea (lungimea laturii, exprimată în unităţi);
• coordonatele centrului;
• altitudinea la care survolează.

Pentru a genera o rază laser distrugătoare, flota de OZN-uri trebuie să se poziţioneze unul sub altul astfel încât centrele lor să fie aliniate pe verticală. OZN-urile se pot mişca după următoarele reguli:

• îşi menţin altitudinea constantă;
• pot zbura paralel cu axele hărţii Bucureştiului;
• nu se pot ciocni de clădiri, dar pot zbura pe deasupra lor;
• nu pot părăsi, cu nicio parte a lor, perimetrul Bucureştiului (Ilfovul le dăunează).

Pentru a-şi pregăti apărarea, Primăria doreşte, în primă fază, să afle deasupra câtor clădiri distincte s-ar putea alinia centrele OZN-urilor.

Date de intrare

Fişierul de intrare ozn.in conţine pe prima linie trei numere M N K, despărţite prin spaţii. M şi N sunt numărul de linii şi de coloane al hărţii Bucureştiului, iar K este numărul de OZN-uri. Pe următoarele M linii se află câte N numere indicând înălţimile clădirilor Bucureştiului. Pe următoarele K linii se află descrierea câte unui OZN, indicată prin patru numere naturale L C D A cu semnificaţiile:

• L - linia pe care se află centrul OZN-ului;
• C - coloana pe care se află centrul OZN-ului;
• D - dimensiunea laturii;
• A - altitudinea.

Date de ieşire

În fişierul de ieşire ozn.out se va scrie un singur număr, reprezentând numărul de coordonate la care OZN-urile se pot alinia.

Restricţii

• 1 ≤ M, N ≤ 200
• 1 ≤ K ≤ 100
• înălţimile clădirilor şi altitudinile OZN-urilor sunt cuprinse între 1 şi 50.000
• pentru fiecare OZN:
  • 1 ≤ L ≤ M
  • 1 ≤ C ≤ N
  • 1 ≤ D ≤ min(M, N), iar D este întotdeauna impar

Exemplu

ozn.in	ozn.out
5 7 2 3 8 12 9 15 3 1 2 9 5 9 10 1 7 7 23 10 12 17 5 11 8 4 12 6 19 3 55 18 7 3 9 12 10 3 4 1 1 10 2 6 3 20	2

Explicaţie

Primul OZN are mărimea 1×1 (cât amprenta unei clădiri) şi zboară la altitudinea 10. El poate atinge zonele roşii din prima figură de mai jos.

Al doilea OZN are mărimea 3×3 şi zboară la altitudinea 20. Centrul său poate atinge zonele albastre din a doua figură de mai jos.

OZN-urile îşi pot alinia centrele în două locuri: la coordonatele (2, 4) şi (4, 4).