Editing 3368 - Lee2

Bil Gheiț, patronul Companiei Macrosoft, vă pune la dispoziție o matrice cu <code>n</code> linii, numerotate de la <code>1</code> la <code>n</code> și <code>n</code> coloane, numerotate de la <code>1</code> la <code>n</code>, care memorează numere naturale. Un drum în matrice care pornește de la poziția <code>(1,1)</code> și se termină la poziția <code>(n,n)</code> 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 <code>(1,1)</code> și se termină la poziția <code>(n,n)</code> ș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 <code>n</code>, <code>X</code>, <code>Y</code>, <code>Z</code>, <code>T</code>, iar apoi exact <code>n</code> numere naturale reprezentând prima linie din matrice. Restul elementelor se vor genera după formula: <code>a[i][j] = 1 + (a[i-1][j-1] * X + a[i-1][j] * Y + a[i-1][j+1] * Z) % T</code>, <code>i=2..n</code>, <code>j=1..n</code>. Se observă că unele elemente din formulă pot fi <code>0</code>, de exemplu, atunci când se calculează valoarea lui <code>a[2,1]</code> care depinde de <code>a[1, 0]</code>.

= Date de ieșire =
Programul va afișa la ecran, ca să vadă și Bil, suma minimă a unui drum de la <code>(1,1)</code> la <code>(n,n)</code>.

= Restricții și precizări =

* <code>1 ≤ n ≤ 1500</code>
* <code>1 ≤ X, Y, Z, T ≤ 500</code>
* <code>1 ≤ a[i,j] ≤ 500</code>, pentru orice <code>i=1..n</code>, <code>j=1..n</code>

= 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>