Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Spacer po linie (spacer-lin) Memory limit: 32 MB Time limit: 1.00 s Małpka Bajtozja spaceruje po linie w cyrku. Lina jest podzielona na N kawałków jednostkowych. Małpka jest w stanie wykonać krok o jeden lub o dwa kawałki jednostkowe do przodu. Niestety, niektóre miejsca liny są niebezpieczne – dla każdego kawałka jednostkowego małpka określiła jego współczynnik niebezpieczeństwa. Małpka chce przejść przez linę przy zminimalizowaniu sumarycznego współczynnika. Małpka startuje zaraz przed pierwszym kawałkiem jednostkowym (w pierwszym kroku może przeskoczyć albo na pierwszy albo na drugi kawałek jednostkowy), a kończy zaraz za ostatnim kawałkiem jednostkowym (w ostatnim kroku może przeskoczyć albo z ostatniego albo z przedostatniego kawałka jednostkowego). Napisz program, który: wczyta opis liny, wyznaczy minimalny sumaryczny współczynnik niebezpieczeństwa przejścia liny i wypisze wynik na standardowe wyjście. Wejście W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę kawałków jednostkowych, na które podzielona jest lina. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb całkowitych pooddzielanych pojedynczymi odstępami – i-ta liczba określa współczynnik niebezpieczeństwa i-tego kawałka jednostkowego liny. Wyjście W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – minimalny sumaryczny współczynnik niebezpieczeństwa dla optymalnej trasy Bajtozji. Ograniczenia 1 ≤ N ≤ 1 000 000, 0 ≤ Ai ≤ 109. Przykład Input Output Explanation 6 3 0 1 5 2 1 3 Małpka może skoczyć na drugi kawałek jednostkowy, potem przeskoczyć na trzeci, następnie na piąty kawałek jednostkowy, by finalnie przeskoczyć poza linę. Łączny współczynnik niebezpieczeństwa wyniesie wówczas: 0 + 1 + 2 = 3.

Input	Output	Explanation
`6 3 0 1 5 2 1`	`3`	Małpka może skoczyć na drugi kawałek jednostkowy, potem przeskoczyć na trzeci, następnie na piąty kawałek jednostkowy, by finalnie przeskoczyć poza linę. Łączny współczynnik niebezpieczeństwa wyniesie wówczas: 0 + 1 + 2 = 3.