Fişierul intrare/ieşire: | ozn.in, ozn.out | Sursă | Baraj Shumen juniori 2014 - etapa 2 |
Autor | Cristian Francu | Adăugată de | |
Timp execuţie pe test | 0.4 sec | Limită de memorie | 16384 kbytes |
Scorul tău | N/A | Dificultate |
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).
![]() | ![]() |