3368 - Lee2

Bil Gheiț, patronul Companiei Macrosoft, vă pune la dispoziție o matrice cu n linii, numerotate de la 1 la n și n coloane, numerotate de la 1 la n, care memorează numere naturale. Un drum în matrice care pornește de la poziția (1,1) și se termină la poziția (n,n) este constituit din componente adiacente două câte două pe linii și coloane. Costul drumului este egal cu suma costurilor componentelor prin care trece drumul.

Cerința

Determinați costul minim al unui drum care pornește de la poziția (1,1) și se termină la poziția (n,n) și domnul Bil Gheiț vă va angaja imediat la compania sa pe post de fochist.

Date de intrare

Pentru toate testele, matricea se va genera aleator. Se citesc de la tastatură mai întâi numerele naturale n, X, Y, Z, T, iar apoi exact n numere naturale reprezentând prima linie din matrice. Restul elementelor se vor genera după formula: a[i][j] = 1 + (a[i-1][j-1] * X + a[i-1][j] * Y + a[i-1][j+1] * Z) % T, i=2..n, j=1..n. Se observă că unele elemente din formulă pot fi 0, de exemplu, atunci când se calculează valoarea lui a[2,1] care depinde de a[1, 0].

Date de ieșire

Programul va afișa la ecran, ca să vadă și Bil, suma minimă a unui drum de la (1,1) la (n,n).

Restricții și precizări

• 1 ≤ n ≤ 1500
• 1 ≤ X, Y, Z, T ≤ 500
• 1 ≤ a[i,j] ≤ 500, pentru orice i=1..n, j=1..n

Exemplu:

Intrare

8 21 23 57 31
253 416 101 476 248 159 387 209 

Ieșire

446

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1"> import heapq

nmax = 1505 oo = 1e9

class Element:

   def __init__(self, cost, x, y):
       self.cost = cost
       self.x = x
       self.y = y
   
   def __lt__(self, other):
       return self.cost > other.cost

a = [[0] * nmax for _ in range(nmax)] n = 0 d = [[oo] * nmax for _ in range(nmax)] q = []

def Citire():

   global n
   X, Y, Z, T = map(int, input().split())
   n = int(input())
   a[1] = list(map(int, input().split()))
   for i in range(2, n + 1):
       for j in range(1, n + 1):
           a[i][j] = 1 + (a[i-1][j-1] * X + a[i-1][j] * Y + a[i-1][j+1] * Z) % T

def Interior(i, j):

   if i < 1 or i > n or j < 1 or j > n:
       return False
   return True

def Lee():

   dx = [0, 0, -1, 1]
   dy = [-1, 1, 0, 0]
   
   for i in range(1, n + 1):
       for j in range(1, n + 1):
           d[i][j] = oo
   
   w = Element(a[1][1], 1, 1)
   heapq.heappush(q, w)
   d[1][1] = a[1][1]
   
   while q:
       i, j = heapq.heappop(q).x, heapq.heappop(q).y
       for k in range(4):
           x = i + dx[k]
           y = j + dy[k]
           if Interior(x, y) and d[x][y] > a[x][y] + d[i][j]:
               w = Element(a[x][y] + d[i][j], x, y)
               d[x][y] = a[x][y] + d[i][j]
               heapq.heappush(q, w)
   
   print(d[n][n])

Citire() Lee()

</syntaxhighlight>