Матроска
|
|
1 | |
Задача об удалении трех элементов последовательности14.10.2014, 15:47. Показов 546. Ответов 0
Метки нет (Все метки)
В школьном (!) туре олимпиады по информатике была такая задача:
Удаление Ограничение времени: 2 с Ограничение памяти: 256 M У Гудвина есть последовательность чисел из которой он хочет удалить три элемента так, чтобы последовательность была наиболее симпатичной, то есть, наименее кривой. Кривизна последовательности задается разностью между суммой элементов, стоящих на нечетных местах, и суммой элементов, стоящих на четных местах. После удаления из последовательности трех элементов все остальные сдвигаются на соответствующие места. Например, из последовательности {1,2,3,4,5} можно получить последовательность {2,4}. Формат входных данных В первой строке записано целое число n (4 ≤ n ≤ 106) — количество элементов в исходной последовательности. Во второй строке записаны n разделенных пробелами целых чисел — члены последовательности, разделенные пробелами. Все числа в последовательности по модулю не превышают 109. Тесты поделены на несколько групп, но оцениваются отдельно. n ≤ 81 — +20 баллов n ≤ 300 — +10 баллов n ≤ 5000 — +20 баллов Без дополнительных ограничений — +50 баллов Формат выходных данных Выведите единственное число — минимальную кривизну последовательности, которая может быть получена из данной удалением трех элементов. Примеры Входные данные 4 1 2 3 4 Результат работы 1 Входные данные 5 1 2 3 4 5 Результат работы -4 Написать полный перебор оказалось несложно. Но эта программа, естественно, не проходит большинство тестов по времени. Более оптимальный алгоритм придумать никак не могу. Поиск тоже не помог. Помогите, пожалуйста. Теперь эту задачу решать вовсе не обязательно, но решить хочется. |
14.10.2014, 15:47 | |
Ответы с готовыми решениями:
0
Найти наибольшую сумму трех нечетных элементов последовательности Найти последовательности из трех элементов, сумма которых больше 10 Найти максимум среди последних трех элементов последовательности Определить, сколько в этой последовательности одно-, двух-, трех-, четырех- значных элементов |
14.10.2014, 15:47 | |