Fișierul intrare/ieșire becuri1.in, becuri1.out Sursă Test verificare Nerdvana, ian. 2024
Autor Cristian Frâncu Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 6 sec Limită de memorie 32768 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Becuri1 (clasa a 7-a)

O zonă de deal trebuie modernizată prin amplasarea unor stâlpi de iluminare, ce conțin becuri la vârf. Becurile vor fi plasate în formă de matrice, cunoscându-se înălțimile lor. Becurile sunt identice și luminează pe linie și pe coloană maxim K pătrățele adiacente, însă iluminarea nu poate depăși o înălțime strict mai mare. Cu alte cuvinte un bec luminează în cele patru direcții până la distanța D = min(K, i) unde i este distanța până la primul bec situat la o înălțime strict mai mare decât cea a becului curent.

Cerință

Date înălțimile tuturor becurilor să se afișeze numărul maxim de pătrățele iluminate de un singur bec.

Date de intrare

Fișierul de intrare becuri1.in conține pe prima linie M, N și K, numerele de linii, respectiv de coloane ale matricei de iluminat și numărul maxim de pătrățele iluminate de un bec în orice direcție. Pe următoarele M linii conține câte N numere separate prin câte un spațiu reprezentând înălțimile de amplasare ale becurilor.

Date de ieșire

În fișierul de ieșire becuri1.out veți afișa numărul maxim de pătrățele iluminate de un singur bec.

Restricții

  • 5 ≤ M, N ≤ 2000
  • 0 ≤ K ≤ 1999 (K = 0 înseamnă că becul luminează doar pătrățica în care se află el)
  • 0 ≤ înălțimile din matrice ≤ 30 000

Exemplu

becuri1.in becuri1.out Explicații
6 5 2
5 1 9 9 0
4 9 8 5 1
3 8 8 8 5
2 7 3 6 6
1 5 8 7 0
5 9 9 1 9
8
Avem 6 × 5 becuri, care luminează la distanță 2.
 
Becul de la poziția (3 3) de înălțime 8 luminează o pătrățică în sus
și câte două pe celelalte direcții. Cumulat cu el însuși el luminează 8 pătrățele.
8 9 3
4 14 2 3 7 11 14 5 2
4 8 15 5 1 2 9 11 7
12 3 1 8 9 14 3 5 13
8 1 10 9 5 8 11 8 15
6 6 4 8 11 13 7 0 14
9 10 9 1 6 12 2 14 5
0 1 10 13 9 12 7 2 1
15 13 10 15 3 0 3 12 11
12
Avem 8 × 9 becuri ce luminează la distanță 3.
 
Becul de la poziția (3 6) de înălțime 14 luminează două pătrățele în sus
și câte trei pe celelalte direcții. Cumulat cu el însuși el luminează 12 pătrățele.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii