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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Lee2:

#include <bits/stdc++.h>
#define nmax 1505
#define oo 1e9
using namespace std;

struct Element
{
    int cost, x, y;

    bool operator<(const Element &A) const
    {
        return cost > A.cost;
    }
};

int a[nmax][nmax], n;
int d[nmax][nmax];
priority_queue <Element> q;

void Citire()
{
    int X, Y, Z, T, i, j;
    cin >> n >> X >> Y >> Z >> T;
    for (int i = 1; i <= n; i++)
        cin >> a[1][i];
    for (i = 2; i <= n; i++)
        for (j = 1; j <= n; j++)
            a[i][j] = 1 + (a[i-1][j-1] * X + a[i-1][j] * Y + a[i-1][j+1] * Z) % T;
}

inline bool Interior(int i, int j)
{
    if (i < 1 || i > n || j < 1 || j > n)
        return false;
    return true;
}

void Lee()
{
    int dx[] = {0, 0, -1, 1};
    int dy[] = {-1, 1, 0, 0};
    int i, j, x, y, k;
    Element w;
    /// init
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            d[i][j] = oo;
    w.x = w.y = 1;
    w.cost = a[1][1];
    q.push(w);
    d[1][1] = a[1][1];
    while (!q.empty())
    {
        i = q.top().x;
        j = q.top().y;
        q.pop();
        for (k = 0; k < 4; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (Interior(x, y) && d[x][y] > a[x][y] + d[i][j])
            {
                w.cost = d[x][y] = a[x][y] + d[i][j];
                w.x = x;
                w.y = y;
                q.push(w);
            }
        }
    }
    cout << d[n][n] << "\n";
}

int main()
{
    Citire();
    Lee();

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3368 Lee2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3368 Lee2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3368 Lee2