Pe țărmul insulei Mauritius sunt N localități, numerotate de la 1 la N, considerate puncte de maximă atracție pentru turiști. Acestea sunt conectate printr-o rețea feroviară cu linie ferată dublă ce leagă localitățile 1 de 2, 2 de 3, … , N-1 de N și N de 1, putându-se realiza astfel două circuite. Primul circuit presupune vizitarea localităţilor 1 2 .., N 1, în această ordine, iar cel de-al doilea, vizitarea localităţilor 1 N N – 1 … 2 1. În fiecare localitate există agenții ale tuturor celor M operatori de turism, numerotați de la 1 la M.

Un tichet de călătorie se poate achiziționa doar din localitatea în care se găsește călătorul și permite deplasarea din acea localitate până la următoarea localitate a circuitului. Pentru fidelizarea clienților, operatorii de turism utilizează următoarea regulă pentru prețurile tichetelor: dacă un călător a ajuns într-o gară, cu un tichet cumpărat de la un anumit operator de turism și își continuă călătoria către următoarea destinație cu un tichet pe care-l va cumpăra de la un alt operator de turism, atunci noul tichet își va dubla prețul.

Ștefan se află în concediu pe insulă în localitatea 1 și tocmai a câștigat un premiu oferit de operatorul de turism numerotat cu 1, pentru o excursie cu N tichete de călătorie pe insula Mauritius.

El pornește din localitatea în care se află și apoi parcurge cu trenul întregul circuit, astfel încât cu ultimul tichet cumpărat să se întoarcă în localitatea 1, de unde a plecat. Același operator de turism îi oferă contra cost, primul tichet de călătorie. Ștefan va studia toate ofertele și dacă e cazul poate refuza inclusiv acest prim tichet pentru a-l achiziționa de un alt operator de turism, chiar dacă i se va dubla prețul (fiindcă a schimbat operatorul).

Cerinţă

Cunoscând prețul tichetelor de călătorie, stabilite de fiecare operator de turism, determinați suma minimă cu care Ștefan poate achiziționa cele N tichete necesare călătoriei sale.

Date de intrare

Fişierul de intrare insula.in conţine:

pe prima linie două numere naturale N și M, despărțite printr-un spațiu cu semnificația din enunț;
pe următoarele M linii, câte N numere naturale p[i,1], p[i,2], … , p[i,n], separate prin câte un spațiu. Valorile de pe linia i+1, reprezintă în ordine, prețurile stabilite de operatorul numerotat cu i pentru achiziționarea tichetelor de călătorie între localitățile 1 și 2, 2 și 3, …, N-1 și N, respectiv N și 1.

Date de ieșire

Fişierul de ieşire insula.out va conţine pe prima linie un singur număr natural ce reprezintă suma minimă cu care Ștefan poate achiziționa cele N tichete pentru călătoria sa.

Restricții și precizări

3 ≤ N < 300, N număr impar;
1 ≤ M < 300
prețurile tichetelor sunt numere naturale nenule cu cel mult două cifre fiecare;
pentru 40% din punctaj, N < 10

Exemplu

insula.in

3 2
10 9 3
2 8 5

insula.out

Explicație

Pe circuit sunt 3 localități și 2 operatori de turism.

Operatorul 1 are următoarele prețuri: pentru deplasarea între localitățile 1 și 2 tichetul are prețul 10, între localitățile 2 și 3 tichetul are prețul 9 iar între localitățile 3 și 1, tichetul are prețul 3.

Operatorul 2 are următoarele prețuri: pentru deplasarea între localitățile 1 și 2 tichetul are prețul 2, între localitățile 2 și 3 tichetul are prețul 8 iar între localitățile 3 și 1, tichetul are prețul 5. Un traseu parcurs cu 3 tichete, poate fi: 1→3 preț 3 , 3→2 preț 9 , 2→1 cu preț 2 de la operatorul 2,(prețul se dublează). Cost minim total 3+9+2*2=16

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 Insula:

//prof.Eugen Nodea

# include <fstream>
# include <algorithm>
# define inf 999999999
# define NM 305
using namespace std;

ifstream f("insula.in");
ofstream g("insula.out");

int i, j, n, m, Min1;
int a[NM][NM], cost[NM][NM], Min[NM];

void init ()
{
    for (int i=1; i<=n+1; ++i)
    {
        Min[i] = inf;
        for (int j=1; j<=m; ++j)
            a[i][j] = inf;
    }
}

int main ()
{
    f >> n >> m;
    for (i=1; i<=m; ++i)
        for (j=1; j<=n; ++j)
            f >> cost[i][j+1];

    //cost[i][j]- costul pentru a merge cu transportatorul i in j
    //a[i][j]   - costul minim pt a ajunge la a i-a statie cu transportatorul j

    init ();
    for (i=1; i<=m; ++i)
    {
        if (i == 1) a[2][i] = cost[i][2];
               else a[2][i] = cost[i][2] * 2;
        Min[2] = min(Min[2], a[2][i]);
    }
    for (i=3; i<=n+1; ++i)
    {
        for (j=1; j<=m; ++j)
        {
            a[i][j] = min(a[i-1][j] + cost[j][i], Min[i-1] + 2 * cost[j][i]);
             Min[i] = min(Min[i], a[i][j]);
        }
    }

    Min1 = Min[n+1];

    init ();
    for (i=1; i<=m; ++i)
    {
         if (i == 1) a[n][i] = cost[i][n+1];
                else a[n][i] = cost[i][n+1] * 2;
        Min[n] = min(Min[n], a[n][i]);
    }

    for (i=n-1; i>=1; --i)
    {
        for (j=1; j<=m; ++j)
        {
            a[i][j] = min(a[i+1][j] + cost[j][i+1], Min[i+1] + 2 * cost[j][i+1]);
             Min[i] = min(Min[i], a[i][j]);
        }
    }

    g << min(Min1, Min[1]) << "
";

    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 #1243 Insula

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1243 Insula 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 #1243 Insula