Задача об удалении трех элементов последовательности

14.10.2014, 15:47. **Показов** 546. **Ответов** 0

Author24 — интернет-сервис помощи студентам

В школьном (!) туре олимпиады по информатике была такая задача:

Удаление
Ограничение времени: 2 с
Ограничение памяти: 256 M
У Гудвина есть последовательность чисел из которой он хочет удалить три элемента так, чтобы последовательность была наиболее симпатичной, то есть, наименее кривой.
Кривизна последовательности задается разностью между суммой элементов, стоящих на нечетных местах, и суммой элементов, стоящих на четных местах.
После удаления из последовательности трех элементов все остальные сдвигаются на соответствующие места. Например, из последовательности {1,2,3,4,5} можно получить последовательность {2,4}.

Формат входных данных
В первой строке записано целое число n (4 ≤ n ≤ 10⁶) — количество элементов в исходной последовательности. Во второй строке записаны n разделенных пробелами целых чисел — члены последовательности, разделенные пробелами. Все числа в последовательности по модулю не превышают 10⁹.

Тесты поделены на несколько групп, но оцениваются отдельно.
n ≤ 81 — +20 баллов
n ≤ 300 — +10 баллов
n ≤ 5000 — +20 баллов
Без дополнительных ограничений — +50 баллов
Формат выходных данных
Выведите единственное число — минимальную кривизну последовательности, которая может быть получена из данной удалением трех элементов.

Примеры
Входные данные
4
1 2 3 4
Результат работы
1
Входные данные
5
1 2 3 4 5
Результат работы
-4
Написать полный перебор оказалось несложно. Но эта программа, естественно, не проходит большинство тестов по времени.
Более оптимальный алгоритм придумать никак не могу. Поиск тоже не помог.
Помогите, пожалуйста. Теперь эту задачу решать вовсе не обязательно, но решить хочется.

Матроска
		1
	Задача об удалении трех элементов последовательности 14.10.2014, 15:47. Показов 546. Ответов 0 Метки нет (Все метки) В школьном (!) туре олимпиады по информатике была такая задача: Удаление Ограничение времени: 2 с Ограничение памяти: 256 M У Гудвина есть последовательность чисел из которой он хочет удалить три элемента так, чтобы последовательность была наиболее симпатичной, то есть, наименее кривой. Кривизна последовательности задается разностью между суммой элементов, стоящих на нечетных местах, и суммой элементов, стоящих на четных местах. После удаления из последовательности трех элементов все остальные сдвигаются на соответствующие места. Например, из последовательности {1,2,3,4,5} можно получить последовательность {2,4}. Формат входных данных В первой строке записано целое число n (4 ≤ n ≤ 10⁶) — количество элементов в исходной последовательности. Во второй строке записаны n разделенных пробелами целых чисел — члены последовательности, разделенные пробелами. Все числа в последовательности по модулю не превышают 10⁹. Тесты поделены на несколько групп, но оцениваются отдельно. 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

Опции темы