1486 - Gropi

From Bitnami MediaWiki
Revision as of 21:52, 28 December 2023 by Vasiliu Costel Andrei (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Enunț

Gigel a primit de la prietenul său Programatorul o hartă a grădinii acestuia. Grădina are forma dreptunghiulară şi harta pe care a primit-o Gigel conţine informaţii despre starea culturii de pomi fructiferi. Mai precis ea conţine înălţimile fiecărui copac şi zonele în care s-au săpat gropi dar încă nu au fost plantaţi copaci. Harta grădinii poate fi reprezentată sub forma unei table dreptunghiulare cu N linii, numerotate de la 1 la N de sus în jos, şi M coloane, numerotate de la 1 la M de la stânga la dreapta. În fiecare celulă se află un număr real corespunzător înălţimii copacului sau valoarea 0 corespunzătoare unei gropi.

Cerința

Cunoscând coordonatele unui punct de pe hartă ajutaţi-l pe Gigel să determine pe care dintre cele 8 direcţii N, NE, E, SE, S, SV, V, NV corespunzătoare acestui punct se află cele mai multe gropi.

Date de intrare

Fișierul de intrare gropiin.txt conține pe prima linie patru numere: N, M reprezentând dimensiunile grădinii şi X, Y reprezentând coordonatele unui punct de pe hartă – linie şi coloană. Pe următoarele N linii sunt şiruri de câte M numere corespunzătoare copacilor respectiv gropilor.

Date de ieșire

Fișierul de ieșire gropiout.txt va conține pe prima linie direcţia pe care se află cele mai multe gropi şi numărul acestora separate printr-un spațiu. Direcţia este indicată prin una din următoarele valori: N, NE, E, SE, S, SV, V, NV. Dacă sunt două direcţii cu acelaşi număr de gropi se va afişa ultima direcţie considerând sensul orar.

Restricții și precizări

  • 1 ⩽ N, M ⩽ 1.000
  • 1 ⩽ XN, 1 ⩽ YM

Exemplul 1

Intrare
gropiin.txt
4 6 3 3
2.2 4.5 0 4.3 0 8.5
6.8 0 9.4 0 7.5 9.3
1.7 0 2.6 4.7 0 0
0 3.2 6.3 8.1 5.2 2.2
Ieșire
Datele de intrare corespund restricțiilor impuse
gropiout.txt
E 2

Explicație

Din punctul de coordonate 3 3 pe direcţiile:

  • SE, S, SV nu se află nicio groapă
  • N, V, NV se afla câte o groapă
  • NE, E se află câte 2 gropi.

Se va afişa ultima direcţie considerând sensul orar.

Exemplul 2

Intrare
gropiin.txt
1001 6 3 3
2.2 4.5 0 4.3 0 8.5
6.8 0 9.4 0 7.5 9.3
1.7 0 2.6 4.7 0 0
0 3.2 6.3 8.1 5.2 2.2
Ieșire
Datele de intrare NU corespund restricțiilor impuse

Rezolvare

<syntaxhighlight lang="python" line>

  1. 1486 - Gropi

def validare_date(n, m, x, y):

   if not (1 <= n <= 1000) or not (1 <= m <= 1000):
       return False
   if not (1 <= x <= n) or not (1 <= y <= m):
       return False
   return True


def numar_gropi_directie(harta, directie, x, y):

   directii = {
       'N': (-1, 0),
       'NE': (-1, 1),
       'E': (0, 1),
       'SE': (1, 1),
       'S': (1, 0),
       'SV': (1, -1),
       'V': (0, -1),
       'NV': (-1, -1)
   }
   dx, dy = directii[directie]
   numar_gropi = 0
   while 1 <= x <= len(harta) and 1 <= y <= len(harta[0]):
       if harta[x - 1][y - 1] == 0:
           numar_gropi += 1
       x, y = x + dx, y + dy
   return numar_gropi


def determina_directie_maxima(x, y, harta):

   directii = ['N', 'NE', 'E', 'SE', 'S', 'SV', 'V', 'NV']
   max_gropi = -1
   directie_maxima = None
   for directie in directii:
       x_temp, y_temp = x, y
       numar_gropi = numar_gropi_directie(harta, directie, x_temp, y_temp)
       if numar_gropi > max_gropi or (numar_gropi == max_gropi and directie_maxima is not None and directii.index(directie) > directii.index(directie_maxima)):
           max_gropi = numar_gropi
           directie_maxima = directie
   return directie_maxima, max_gropi


def main():

   with open("gropiin.txt", "r") as f:
       n, m, x, y = map(int, f.readline().split())
       harta = [list(map(float, f.readline().split())) for _ in range(n)]
   if validare_date(n, m, x, y):
       print("Datele de intrare corespund restricțiilor impuse")       
       
       directie, numar_gropi = determina_directie_maxima(x, y, harta)
       with open("gropiout.txt", "w") as f:
           f.write(f"{directie} {numar_gropi}\n")
   else:
       print("Datele de intrare NU corespund restricțiilor impuse")
       exit(0)


if __name__ == "__main__":

   main()

</syntaxhighlight>