Fişierul intrare/ieşire:insula.in, insula.outSursăLot III Juniori 2015
AutorCristina IordaicheAdăugată deTiberiu028A Tiberiu Musat Tiberiu02
Timp execuţie pe test0.1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Insula (Lot Juniori)

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 pi1, pi2, ..., pin, 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

  • 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.ininsula.outExplicaţii
3 2
10 9 3
2 8 5
16
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici