Raul: Pagină nouă: 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...

2023-12-21T16:01:38Z

Pagină nouă: 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...

New page

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>

3368 - Lee2 - Revision history