Fişierul intrare/ieşire:ozn.in, ozn.outSursăad-hoc
AutorCristian FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.4 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inozn.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici