3686 - Vaccination

Cerință

Echipa V.R.N.C. a dezvoltat un vaccin contra celei mai recente boli. Vaccinul este distribuit mai întâi unei singure persoane, iar mai apoi se împrăștie celor 4 vecini(populația este reprezentată pe o matrice de dimensiunile n și m). Ulterior, fiecare persoana va da vaccinul celor 4 vecini până când o persoană de la marginea matricii este vaccinată, moment în care vaccinul nu mai este dat mai departe.

Vazând succesul acestei metode, V.R.N.C ne dă o matrice în care știm vârsta fiecărei persoane și trebuie să aflăm punctul unde V.R.N.C ar trebui să înceapă distribuția vaccinului astfel încât să maximizăm suma vârstelor oamenilor vaccinați.

Date de intrare

Programul citește de la tastatură pe prima linie numerele n și m, iar apoi n linii, fiecare linie conținând m numere separate prin spații, reprezentând vârstele celor n*m cetățeni

Date de ieșire

Programul va afișa pe ecran două valori i și j, locul unde vaccinarea ar trebui să înceapă. Dacă sunt mai multe soluții, trebuie afișată cea mai din stânga-sus poziție.

Restricții și precizări

1 ≤ n, m ≤ 1000

cele n*m numere citite vor fi între 0 și 2147483647

Exemplu:

Intrare

3 4

1 2 3 4

5 6 7 8

9 10 11 12

Ieșire

2 3

Explicație

Începând de la celula (2, 3) cu valoarea 7, vaccinul va ajunge și la valorile 3, 6, 8 și 11, suma fiind 35, aceasta fiind suma maximă posibilă obținută.

Rezolvare

def get_vecini(matrice, i, j):

    vecini = []

    randuri, coloane = len(matrice), len(matrice[0])

    # Verificăm vecinii de sus, jos, stânga și dreapta și îi adăugăm în lista "vecini"

    if i > 0:

        vecini.append(matrice[i - 1][j])

    if i < randuri - 1:

        vecini.append(matrice[i + 1][j])

    if j > 0:

        vecini.append(matrice[i][j - 1])

    if j < coloane - 1:

        vecini.append(matrice[i][j + 1])

    return vecini

def maximizeaza_distributia_vaccinului(matrice):

    suma_maxima = 0

    start_i, start_j = 0, 0

    randuri, coloane = len(matrice), len(matrice[0])

    # Iterăm prin matrice, excludem marginea superioară și inferioară

    for i in range(1, randuri - 1):

        for j in range(coloane):

            # Calculăm suma vârstei curente și a vecinilor

            suma_curenta = matrice[i][j]

            vecini = get_vecini(matrice, i, j)

            suma_curenta += sum(vecini)

            # Verificăm dacă suma curentă este mai mare decât suma maximă

            if suma_curenta > suma_maxima:

                suma_maxima = suma_curenta

                start_i, start_j = i, j

    return start_i, start_j + 1  # Adăugăm 1 pentru a afișa poziția corectă

# Citire date de intrare

n, m = map(int, input().split())

varste_matrice = [list(map(int, input().split())) for _ in range(n)]

# Calcul și afișare rezultat

start_i, start_j = maximizeaza_distributia_vaccinului(varste_matrice)

print(f"Locul de start pentru vaccinare: ({start_i + 1}, {start_j})")