Московская олимпиада по информатике - 2005: различия между версиями
Содержимое удалено Содержимое добавлено
Se0808 (обсуждение | вклад) м переименовал «Московская олимпиада по информатике» в «Московская олимпиада по информатике - 2005»: других годов пока нет |
Se0808 (обсуждение | вклад) Нет описания правки |
||
Строка 1:
<div style="border:thin solid #430; background:#f9fff8;margin:0.8em;padding:1em;">Уважаемые участники олимпиады! На этой странице вы можете не только ознакомиться с разборами задач, подготовленных жюри, но и внести свой вклад в улучшение этих текстов, пользуясь вкладкой "править": исправить ошибки и опечатки, добавить свои комментарии, предложения, другие варианты алгоритмов и т. п. Обсудить возникшие вопросы можно на странице "обсуждение", посмотреть исходный вариант этого текста - на странице "история".</div>
Здесь размещены задачи очного тура 2005/06 учебных годов. Условия задач доступны на официальном сайте олимпиады: [http://
▲Условия задач доступны на официальном сайте олимпиады: http://www.olympiads.ru/moscow
''Автор задачи и разбора – В.М.Гуровиц''
Строка 90 ⟶ 89 :
Существует множество других алгоритмов, решающих задачу за время ''O(N log N)'' или ''O(N<sup>2</sup>)'', что удовлетворяет приведенным в задаче ограничениям. Но реализация этих алгоритмов не проще, а зачастую сложнее приведенной в этом разборе реализации линейного алгоритма.
''Автор разбора – В.М.Гуровиц''
Строка 134 ⟶ 133 :
end;
''Автор задачи и разбора - А.Ю.Гусаков''
Строка 249 ⟶ 248 :
Оказывается, что приведенную динамическую схему можно упростить. Достаточно для каждого числа m хранить информацию лишь о самом коротком выражении, независимо от его типа. При этом, если для данного числа самое короткое выражение может быть как выражением типа 1, так и выражением типа 2, то нужно выбирать произведение, а не сумму. Обоснование правильности этого алгоритма оставим читателю.
''Автор задачи и разбора – В.М.Гуровиц''[[Файл:moi_06_1_D1.gif|right|frame|Рис. 1]]
Строка 311 ⟶ 310 :
В приведённой программе мы считывали все числа в двумерный массив. На самом деле в этом нет необходимости: на каждом шаге алгоритма мы используем лишь две последовательные строки чисел, поэтому можно читать строки чисел из файла последовательно, используя лишь два одномерных массива.
''Автор задачи - Е.В.Андреева, авторы разбора - Е.В.Андреева и В.М.Гуровиц ''
Строка 352 ⟶ 351 :
ответ сразу, вычисляя числа в столбцах по мере их печати.
''Автор задачи и разбора - А.П.Лахно''
Строка 404 ⟶ 403 :
3 5
''Автор задачи и разбора - Б.О.Василевский''
Строка 497 ⟶ 496 :
'''''Шаг 3 (сортировка и поиск прямой с максимальной степенью). '''''Теперь отсортируем полученный список по полярному углу и будем действовать как в простом случае (единственное отличие – стартовое значение C может быть отлично от нуля).
''Автор задачи - В.А. Матюхин, автора разбора - В.М.Гуровиц ''
Задача решается моделированием описанного в условии процесса. Будем хранить номера свободных на данный момент тупиков, и список стоящих в тупиках в данный момент электричек (точнее, времена их отправления и номера тупиков, в которых они стоят). Будем читать из файла последовательно информацию о прибывающих электричках. Для каждой прибывающей электрички нам потребуется:
| |||