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; } Depresja (depresja) Memory limit: 256 MB Time limit: 1.50 s Jasio dostał od rodziców na urodziny nowiutki, markowy, pachnący jeszcze fabryką ciąg liczb całkowitych a1, …, aN. Jasio od razu przystąpił do zabawy ciągiem: wybiera losowo fragment (spójny niepusty podciąg) ai, ai + 1, …, aj i wyznacza minimum tego podciągu. Jasio wybiera jednorodnie: wybór każdego podciągu ai, ai + 1, …, aj dla pary indeksów i, j spełniających warunek 1 ≤ i ≤ j ≤ N jest jednakowo prawdopodobny. Niestety, Jasio jest dość depresyjnym dzieckiem: po obejrzeniu ciągu Jasio popada w dziecięcą depresję i rodzice muszą go pocieszać przez m sekund, gdzie m to minimum wybranego przez niego podciągu. Rodzice Jasia chcą przewidzieć, ile czasu będą musieli poświęcić na pocieszanie Jasia. Pomóż im i napisz program, który: wczyta ciąg liczb, który otrzymał Jasio, wyznaczy i wypisze oczekiwany czas depresji Jasia. Wejście W pierwszym wierszu wejścia znajduje się liczba naturalna N, określająca długość ciągu, który dostał Jasio. W drugim wierszu wejścia znajduje się opis ciągu, który dostał Jasio; jest to N liczb naturalnych a1, …, aN pooddzielanych pojedynczymi odstępami. Wyjście W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba rzeczywista: oczekiwana wartość czasu m, przez który rodzice będą musieli pocieszać Jasia. Odpowiedź uznaje się za prawidłową, jeśli błąd względny lub bezwzględny obliczonej wartości nie przekracza 10−6. Ograniczenia 1 ≤ N ≤ 1 000 000, 1 ≤ ai ≤ 1 000 000. Przykład Input Output Explanation 3 1 7 2 2.333333 W tym przykładzie jest 6 możliwych podciągów, (1), (7), (2), (1,7), (7,2), (1,7,2), dla których trzeba będzie pocieszać Jasia przez odpowiednio: 1, 7, 2, 1, 2, 1 sekund. Średni czas pocieszania Jasia to $2\frac{1}{3}$ sekundy. Przykład Input Output Explanation 5 2 2 2 3 3 2.200000 W tym przykładzie jest 15 możliwych podciągów. Dla dwunastu z nich trzeba pocieszać Jasia przez 2 sekundy, dla trzech przez 3 – są to podciągi (3), (3), (3,3). Średni czas pocieszania Jasia to $2\frac{1}{5}$ sekundy.

Input	Output	Explanation
`3 1 7 2`	`2.333333`	W tym przykładzie jest 6 możliwych podciągów, (1), (7), (2), (1,7), (7,2), (1,7,2), dla których trzeba będzie pocieszać Jasia przez odpowiednio: 1, 7, 2, 1, 2, 1 sekund. Średni czas pocieszania Jasia to $2\frac{1}{3}$ sekundy.

Input	Output	Explanation
`5 2 2 2 3 3`	`2.200000`	W tym przykładzie jest 15 możliwych podciągów. Dla dwunastu z nich trzeba pocieszać Jasia przez 2 sekundy, dla trzech przez 3 – są to podciągi (3), (3), (3,3). Średni czas pocieszania Jasia to $2\frac{1}{5}$ sekundy.