Soluții trimise

Rezumat problemă

#1243 Insula

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).

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.

ID   Utilizator Problema Data încărcării Stare
Anca Leuciuc (AncaLeuciuc) Insula 29 Iulie 2020, 15:04 Evaluare finalizată 88
sal sal (cont_pbinfo) Insula 23 Iulie 2020, 23:52 Evaluare finalizată 100
Ionescu Ioan-Dorian (Dory_1) Insula 23 Iulie 2020, 19:21 Evaluare finalizată 100
sal sal (_uwu_) Insula 20 Iulie 2020, 05:39 Evaluare finalizată 100
Louis Vuitton (LV) Insula 02 Iulie 2020, 03:51 Evaluare finalizată 100
Yves Saint-Laurent (YSL) Insula 01 Iulie 2020, 05:22 Evaluare finalizată 100
‭ ‭ (May_9th) Insula 08 Iunie 2020, 13:57 Evaluare finalizată 100
‭ ‭ (May_9th) Insula 08 Iunie 2020, 13:51 Evaluare finalizată 100
Doru Floare (Doruletz) Insula 21 Aprilie 2020, 11:03 Evaluare finalizată 100
Ionel Ionelut (0p) Insula 21 Aprilie 2020, 11:03 Evaluare finalizată 100
Ionel Ionelut (0p) Insula 21 Aprilie 2020, 10:59 Evaluare finalizată 52
Niţă Mihai-Daniel (nmdaniel) Insula 17 Aprilie 2020, 08:50 Evaluare finalizată 100
Quintus Maximus (mquintus) Insula 17 Aprilie 2020, 07:28 Evaluare finalizată 100
Quintus Maximus (mquintus) Insula 17 Aprilie 2020, 07:25 Evaluare finalizată 96
Quintus Maximus (mquintus) Insula 17 Aprilie 2020, 07:23 Evaluare finalizată 96
Quintus Maximus (mquintus) Insula 17 Aprilie 2020, 07:21 Evaluare finalizată 92
Quintus Maximus (mquintus) Insula 17 Aprilie 2020, 07:11 Evaluare finalizată 84
Quintus Maximus (mquintus) Insula 16 Aprilie 2020, 18:34 Evaluare finalizată 0
Matteo Alexandru (Matteoverzotti) Insula 29 Martie 2020, 01:02 Evaluare finalizată 100
Costache Alexandra (alexalexandra2004) Insula 10 Martie 2020, 15:19 Evaluare finalizată 0
Bogdan Theodora (theodora_iulia) Insula 10 Martie 2020, 15:19 Evaluare finalizată 0
Cojocariu Elena (corvigel) Insula 09 Martie 2020, 15:41 Evaluare finalizată 0
Biciușcă Matei (Kenji_inDaShadow) Insula 03 Martie 2020, 21:47 Evaluare finalizată 100
Biciușcă Matei (Kenji_inDaShadow) Insula 03 Martie 2020, 21:42 Evaluare finalizată 40
Bărbuț-Dică Sami (Warriors_Cats_Jay_Feather) Insula 09 Ianuarie 2020, 19:57 Evaluare finalizată 100
C/C++ Java (Nirvana) Insula 08 Ianuarie 2020, 16:37 Evaluare finalizată 100
skylake59 . (skylake59) Insula 13 Decembrie 2019, 22:15 Evaluare finalizată 100
Pelinescu Bianca (Pelinescu_Bianca) Insula 30 Octombrie 2019, 07:20 Evaluare finalizată 0
Pelinescu Bianca (Pelinescu_Bianca) Insula 30 Octombrie 2019, 07:17 Evaluare finalizată 0
neagu denisa (deni_neagu) Insula 19 Octombrie 2019, 10:58 Evaluare finalizată 0
neagu denisa (deni_neagu) Insula 19 Octombrie 2019, 10:57 Evaluare finalizată 0
Ungur Raul (Raultudor123) Insula 09 Octombrie 2019, 13:54 Evaluare finalizată 0
Ungur Raul (Raultudor123) Insula 09 Octombrie 2019, 13:52 Evaluare finalizată 0
this is (the_end) Insula 10 Septembrie 2019, 17:20 Evaluare finalizată 100
Vlad Haivas (Vladth11) Insula 07 Septembrie 2019, 13:10 Evaluare finalizată 88
Vlad Haivas (Vladth11) Insula 07 Septembrie 2019, 12:25 Evaluare finalizată 76
Vlad Haivas (Vladth11) Insula 07 Septembrie 2019, 12:25 Evaluare finalizată E.C
Vlad Haivas (Vladth11) Insula 07 Septembrie 2019, 12:21 Evaluare finalizată 76
Camilla Camilla (camilla) Insula 19 August 2019, 14:25 Evaluare finalizată 100
Mesota Ioan (MESOTRIST_2) Insula 06 Iulie 2019, 12:02 Evaluare finalizată 100
Mesota Ioan (MESOTRIST_1) Insula 04 Iulie 2019, 19:17 Evaluare finalizată 100
perju verzotti luca (lucaperju) Insula 03 Mai 2019, 13:49 Evaluare finalizată 100
perju verzotti luca (lucaperju) Insula 03 Mai 2019, 13:49 Evaluare finalizată 0
perju verzotti luca (lucaperju) Insula 03 Mai 2019, 13:48 Evaluare finalizată 96
perju verzotti luca (lucaperju) Insula 03 Mai 2019, 13:48 Evaluare finalizată 0
perju verzotti luca (lucaperju) Insula 03 Mai 2019, 13:46 Evaluare finalizată 46
Ianc Octavian (Ocktitty) Insula 29 Aprilie 2019, 17:01 Evaluare finalizată 100
Utilizator inexistent Insula 14 Aprilie 2019, 15:14 Evaluare finalizată 100
Peticaru Alexandru (AlexandruPeticaru) Insula 17 Martie 2019, 11:44 Evaluare finalizată 100
Peticaru Alexandru (AlexandruPeticaru) Insula 17 Martie 2019, 11:43 Evaluare finalizată 0