| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_22_06 - Podzial |
Grześ i Staś wypisali sobie na kartce ciąg składający się z n liczb. Chłopcy zdefiniowali wartość tego ciągu jako sumę wartości bezwzględnych różnic kolejnych jego elementów:
W = |a1 - a2| + |a2 - a3| + ... + |an - 1 - an|
Teraz Grześ i Staś zastanawiają się czy mogliby uzyskać mniejszą wartość, gdyby podzielili elementy na dwa ciągi, zachowując ich kolejność. Twoim zadaniem jest wyznaczenie minimalnej sumy wartości tych dwóch ciągów.
Wejście
W pierwszej linii wejścia znajduje się jedna liczba całkowita n ∈ [2;1000] określająca liczbę elementów ciągu.
W kolejnej linii znajduje się n liczb całkowitych z zakresu od 1 do 106 będących wartościami kolejnych elementów ciągu.
Wyjście
Na wyjściu należy wypisać minimalną sumę wartości nowo powstałych ciągów.
Przykład
Wejście
6 1 9 2 10 3 11
Wyjście
4
Wyjaśnienie do przykładu
Sumę wartości równą 4 możemy uzyskać tworząc ciągi: 1 2 3 oraz 9 10 11.
| Dodane przez: | Maciej Boniecki |
| Data dodania: | 2015-04-25 |
| Limit czasu wykonania programu: | 0.200s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM64 GOSU JS-MONKEY |
ukryj komentarze
|
2015-04-26 19:12:59 Bart³omiej Tomara
omg - trzeba czytać ze zrozumieniem - już nieważne XD |
|
|
2015-04-26 18:01:01 Bart³omiej Tomara
Hmm, dzięki za odpowiedź. To jak w przykładzie wyszło 4? Sprawdzamy: |1-2|+|3| = 4 |9-10|+|11| = 12 Suma daje 16 a nie 4.. |
|
|
2015-04-26 17:55:51 Maciej Boniecki
Dwa ciągi nie muszą być równe natomiast wynik dla Twojego przykładu na pewno nie będzie wynosił 1. Podstaw sobie do powyższego wzoru najpierw elementy jednego ciągu, potem drugiego i zsumuj wyniki. |
|
|
2015-04-26 17:47:37 Bart³omiej Tomara
Czy dwa ciągi muszą być równe - nie ma tego w treści zadania. Dla: 1 9 2 10 3 11 mógłby zrobić takie dwa ciągi: 1 2 oraz 9 10 3 11, wynik byłby wtedy 1 a nie 4, chyba że treści zadania nie rozumiem :) |
|
|
2015-04-26 12:37:57 Maciej Boniecki
Dla ciągu jednoelementowego wynikiem jest 0. |
|
|
2015-04-26 12:16:00 Mateusz Bajorek
W takim razie, o ile mogę uzyskać odpowiedź na to pytanie, jak mam liczyć wartość dla ciągu jednoelementowego? |
|
|
2015-04-26 12:13:53 Maciej Boniecki
Taki podział jest dozwolony, ale wynikiem dla tego testu nie jest 1. |
|
|
2015-04-26 12:07:56 Mateusz Bajorek
Jaka jest odpowiedź dla testu: 3 10^6 10^6 1? Czy jest dozwolony podział: 10^6 10^6 1, i końcowy wynik, uzyskany w ten sposób, dla tego testu to 1? |
RSS