Московская олимпиада по информатике - 2005: различия между версиями
Содержимое удалено Содержимое добавлено
D'ohBot (обсуждение | вклад) м робот косметические изменения |
|||
Строка 1:
<div style="border:thin solid #430; background:#f9fff8;margin:0.8em;padding:1em;">Уважаемые участники олимпиады! На этой странице вы можете не только ознакомиться с разборами задач, подготовленных жюри, но и внести свой вклад в улучшение этих текстов, пользуясь вкладкой "править": исправить ошибки и опечатки, добавить свои комментарии, предложения, другие варианты алгоритмов и т. п. Обсудить возникшие вопросы можно на странице "обсуждение", посмотреть исходный вариант этого текста - на странице "история".</div>
== 2005/06 учебный год. Очный тур ==
Условия задач доступны на официальном сайте олимпиады: http://www.olympiads.ru/moscow
=== Задача A. Триангуляция ===
''Автор задачи и разбора – В.М.Гуровиц''
Строка 13:
Если же диагоналей меньше, чем ''N''-3, то в многоугольнике есть хотя бы одна не треугольная грань. Ее поиском мы сейчас и займемся.
[[
Разберем решение задачи на примере 10-угольника с вершинами 1, 2, 3, …, 9, 10 и диагоналями 1 - 6, 2 - 4, 4 - 6, 1 - 7, 7 - 10. Поскольку решение не зависит от того, как именно мы изобразим данный выпуклый многоугольник, расположим его на плоскости таким образом, как показано на рисунке: сторону 1 - 10 расположим горизонтально, а остальные вершины расположим над этой стороной.
Строка 90:
Существует множество других алгоритмов, решающих задачу за время ''O(N log N)'' или ''O(N<sup>2</sup>)'', что удовлетворяет приведенным в задаче ограничениям. Но реализация этих алгоритмов не проще, а зачастую сложнее приведенной в этом разборе реализации линейного алгоритма.
=== Задача B. Палиндром ===
''Автор разбора – В.М.Гуровиц''
Строка 134:
end;
=== Задача C. Представление числа ===
''Автор задачи и разбора - А.Ю.Гусаков''
Строка 149:
Сначала вычислим <tt>a[1,m]</tt>. Поскольку соответствующее выражение представимо в виде '''C'''='''A+B''', нам достаточно перебрать все возможные значения и типы выражений '''A''' и '''B''' и выбрать оптимальную комбинацию. Иными словами, <tt>a[1,m]=min(a[i1,t]+a[i2,m-t]+1)</tt>, где <tt>i1</tt>, <tt>i2</tt> – 1 или 2, а <tt>t <= m/2</tt> (можно считать, что значение '''A''' меньше или равно m/2, иначе '''A''' и '''B''' можно поменять местами). В переменных <tt>how[1,m][1]</tt>, <tt>how[1,m][2]</tt>, <tt>how[1,m][3]</tt> будем хранить те значения <tt>i1</tt>, <tt>t</tt>, <tt>i2</tt> соответственно, при которых достигается минимальное значение.
Теперь вычислим <tt>a[2,m]</tt>. Cоответствующее выражение представимо в виде '''A*B''', где '''A''' и '''B''' – либо выражения второго типа, либо выражения первого типа, взятые в скобки (либо какая-то их комбинация). Будем считать, что значение '''A''' меньше или равно
</math></tt> и <tt>m</tt> делится на <tt>t</tt>.
Строка 249:
Оказывается, что приведенную динамическую схему можно упростить. Достаточно для каждого числа m хранить информацию лишь о самом коротком выражении, независимо от его типа. При этом, если для данного числа самое короткое выражение может быть как выражением типа 1, так и выражением типа 2, то нужно выбирать произведение, а не сумму. Обоснование правильности этого алгоритма оставим читателю.
=== Задача D. Восстанови многоугольник ===
''Автор задачи и разбора – В.М.Гуровиц''[[
Опишем алгоритм восстановления многоугольника по числам в клетках; из этого алгоритма в частности будет следовать, что решение всегда единственное.
Рассмотрим пример, изображенный на рис. 1.[[
Будем восстанавливать границы многоугольника, двигаясь сверху вниз. Начнем с верхней строки. Посмотрим на одну из единиц, стоящую в верхней строке. Верхняя сторона этой клетки не может принадлежать границе многоугольника, поскольку, по условию, многоугольник лежит ''внутри ''листа бумаги. Боковые стороны этой клетки тоже не могут лежать на границе многоугольника, поскольку их концы выходят на границу листа. Следовательно, многоугольнику принадлежит нижняя сторона клетки, см. рис. 2.[[
Мы отметили первые участки границы многоугольника. Уменьшим на 1 числа во всех клетках, границами которых эти участки являются (см. рис. 3).[[
Итак, на первом шаге нашего алгоритма мы восстановили самые верхние горизонтальные стороны нашего многоугольника. Переходим к следующему шагу.
Рассмотрим концы нарисованных нами отрезков. Из каждой из этих точек должна выходить еще одна сторона нашего многоугольника, причем обязательно вниз (см. рис. 4).[[
Как и на первом шаге, уменьшим соответствующие числа в клетках, прилежащих к нарисованным на этом шаге отрезкам. При этом некоторые числа уменьшаться сразу на 2, поскольку у некоторых клеток мы обвели две стороны (см. рис. 6)[[
Итак, на втором шаге мы восстановили все вертикальные отрезки, обведенные во второй сверху строке. Переходим снова к горизонтальным отрезкам, спускаясь на одну клетку вниз.
Во второй строке осталась одна единица. Это означает, что нужно обвести отрезок под этой клеткой, и это единственный отрезок данной горизонтали, принадлежащий границе многоугольника. Обводя его, мы уменьшаем на 1 числа в прилежащих клетках (cм. рис. 7).[[
В этой горизонтали остались две точки, их которых выходит пока только по одному отрезку. На следующем шаге из этих точек проводим вертикальные отрезки вниз, уменьшая числа в клетках (см. рис. 7).[[
И, наконец, мы спускаемся еще ниже и по единицам в третей строке клеток восстанавливаем последний горизонтальный ряд (см. рис. 8).
Строка 311:
В приведённой программе мы считывали все числа в двумерный массив. На самом деле в этом нет необходимости: на каждом шаге алгоритма мы используем лишь две последовательные строки чисел, поэтому можно читать строки чисел из файла последовательно, используя лишь два одномерных массива.
=== Задача E. Распредели призы ===
''Автор задачи - Е.В.Андреева, авторы разбора - Е.В.Андреева и В.М.Гуровиц ''
Строка 317:
Рассмотрим отдельно три случая.
1. Если ''K'' четно и ''N/K'' нечетно, то распределить призы требуемым образом нельзя. Действительно, если стоимости призов равны 1, 2, 3, …, ''N'', то суммарная стоимость всех призов равна ''N''(''N''+1)/2, а каждый участник должен получить призы на сумму
2. Если ''N/K ''четно, то можно раздавать призы змейкой, см. рис. (каждая вертикаль соответствует одной из ''K'' команд).
Строка 352:
ответ сразу, вычисляя числа в столбцах по мере их печати.
=== Задача F. Монополия ===
''Автор задачи и разбора - А.П.Лахно''
Строка 404:
3 5
=== Задача G. Найди прямую ===
''Автор задачи и разбора - Б.О.Василевский''
Строка 426:
Если система координат выбрана стандартным образом, то ('''A''', '''B''') больше нуля тогда и только тогда, когда кратчайший поворот – против часовой стрелки, см.рис.1 (соответственно, ('''A''', '''B''') меньше нуля тогда и только тогда, когда кратчайший поворот – по часовой стрелке, см. рис. 2).
[[
Назовем '''началом''' отрезка
Рассмотрим для начала более простой случай: по отношению к P все отрезки лежат справа и сверху.
Строка 462:
Пусть отрезок XY после возможной симметрии его вершин, описанной выше, перешел в отрезок X'Y'. Если ориентированная площадь ('''PX''', '''PY''') отличается по знаку от ориентированной площади ('''PX'''', '''PY''''), то визуально начало и конец «поменялись местами» (мы по-прежнему называем X` началом, если X – начало и наоборот – концом, если X - конец). То есть при вращении наша прямая сначала встретит конец X`Y`, а потом начало (см. рис. 3). В этом случае надо учитывать, что прямые из области 3 (см. рис. 3) тоже пересекают XY (в алгоритме – шаг 3). Кстати, такое возможно, только если XY – первого типа.
[[
С отрезками второго типа таких неудобств не будет.
Строка 497:
'''''Шаг 3 (сортировка и поиск прямой с максимальной степенью). '''''Теперь отсортируем полученный список по полярному углу и будем действовать как в простом случае (единственное отличие – стартовое значение C может быть отлично от нуля).
=== Задача H. Тупики ===
''Автор задачи - В.А. Матюхин, автора разбора - В.М.Гуровиц ''
| |||