Добавлено спустя 26 минут 37 секунд:
dyvniym через google
Андрей и задача
- Спойлер
- ограничение по времени на тест:2 секунды
ограничение по памяти на тест:256 мегабайт
ввод:стандартный ввод
вывод:стандартный вывод
Для проведения соревнования по программированию Андрею не хватает одной задачи. Но у него есть n друзей, которые всегда рады ему помочь. Он может попросить некоторых из них придумать задачу для соревнования. Про каждого своего друга Андрей знает одно число — вероятность того, что он придумает задачу, если его попросить.
Помогите Андрею выбрать людей, к которым следует обратится. Поскольку ему нужна только одна задача, то Андрей расстроится, если никто не придумает задачу или будет придумано больше одной задачи. Необходимо выбрать такой набор людей, что вероятность того, что Андрей не расстроится, будет максимальной.
Входные данные
В первой строке задано одно целое число n (1 ≤ n ≤ 100) — количество друзей Андрея. Во второй строке задано n вещественных чисел pi (0.0 ≤ pi ≤ 1.0) — вероятность того, что i-й друг сможет придумать задачу. Значения заданы не более чем с 6 знаками после десятичной точки.
Выходные данные
Выведите одно вещественное число — вероятность того, что Андрей не расстроится при оптимальном выборе друзей. Ответ будет засчитан, если он отличается от правильного не более чем на 10 - 9.
Примеры тестов
Входные данные
4
0.1 0.2 0.3 0.8
Выходные данные
0.800000000000
Входные данные
2
0.1 0.2
Выходные данные
0.260000000000
Примечание
В первом примере Андрею выгодно попросить только одного своего друга — наиболее надежного.
Во втором примере Андрею выгодно попросить придумать задачу всех своих друзей. Тогда вероятность того, что будет придумана ровно одна задача равна 0.1·0.8 + 0.9·0.2 = 0.26.
Коля и массив
- Спойлер
- ограничение по времени на тест:2 секунды
ограничение по памяти на тест:256 мегабайт
ввод:стандартный ввод
вывод:стандартный вывод
У Артема есть массив из n целых положительных чисел. Артем решил с ним поиграть. Игра состоит из n ходов. Каждый ход происходит следующим образом. Артем выбирает некоторый элемент массива и удаляет его. За это он получает min(a, b) очков, где a и b — числа, которые были соседями удаленного числа. Если у него нет левого или правого соседа, то Артем не получает никаких очков.
После удаления элемента две части массива склеиваются и получается новый массив, с которым и продолжает играть Артем. Боре стало интересно, какое максимальное суммарное количество очков может получить Артем, играя в эту игру.
Входные данные
В первой строке записано одно целое число n (1 ≤ n ≤ 5·105) — количество элементов в массиве. В следующей строке записано n целых чисел ai (1 ≤ ai ≤ 106) — значения элементов массива.
Выходные данные
В единственной строке выведите одно число — максимальное количество очков, которые может получить Артем.
Примеры тестов
Входные данные
5
3 1 5 2 6
Выходные данные
11
Входные данные
5
1 2 3 4 5
Выходные данные
6
Входные данные
5
1 100 101 100 1
Выходные данные
102
