Московская олимпиада по информатике - 2005: различия между версиями

Содержимое удалено Содержимое добавлено
м Защищена страница «Московская олимпиада по информатике - 2005»: многократный вандализм ([Редактирование=Разрешено только администратор…
Нет описания правки
Строка 1:
<div style="border:thin solid #430; background:#f9fff8;margin:0.8em;padding:1em;">Уважаемые участники олимпиады! На этой странице вы можете не только ознакомиться с разборами задач, подготовленных жюри, но и внести свой вклад в улучшение этих текстов, пользуясь вкладкой «править»: исправить ошибки и опечатки, добавить свои комментарии, предложения, другие варианты алгоритмов и  т.  п. Обсудить возникшие вопросы можно на [[Обсуждение:Московская олимпиада по информатике - 2005|странице обсуждения]], посмотреть исходный вариант этого текста  — на [http://ru.wikibooks.org/w/index.php?title=%D0%9C%D0%BE%D1%81%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D0%BE%D0%BB%D0%B8%D0%BC%D0%BF%D0%B8%D0%B0%D0%B4%D0%B0_%D0%BF%D0%BE_%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B5_-_2005&action=history странице истории].</div>
 
Здесь размещены задачи очного тура 2005/06 учебных годов. Условия задач доступны на официальном сайте олимпиады: [http://olympiads.ru/moscow olympiads.ru].
 
== Задача A. Триангуляция ==
''Автор задачи и разбора  — В.  М.  Гуровиц''
 
Решение задачи разбивается на две части: нужно сначала определить, есть ли не треугольные части, а затем найти одну из них.
Строка 14:
[[Файл:moi06_1_A_1.jpg|center|]]
 
Разберем решение задачи на примере 10-угольника с вершинами 1, 2, 3, …, 9, 10 и диагоналями 1  — 6, 2  — 4, 4  — 6, 1  — 7, 7  — 10. Поскольку решение не зависит от того, как именно мы изобразим данный выпуклый многоугольник, расположим его на плоскости таким образом, как показано на рисунке: сторону 1  — 10 расположим горизонтально, а остальные вершины расположим над этой стороной.
 
Спроецируем все стороны и диагонали на горизонтальную прямую и далее будем рассматривать только эти проекции. Заметим, что поскольку стороны и диагонали многоугольника не пересекались, то и их проекции не пересекаются, то есть любые два отрезка-проекции либо не имеют внутренних точек, либо один из отрезков лежит внутри другого. Назовем отрезок 1  — 10 отрезком ''уровня 1''. Максимальные отрезки, на которые он разбивается (1  — 7 и 7  — 10) назовем отрезками ''уровня 2''. Отрезки, на которые разбиваются отрезки второго уровня, назовем отрезками ''третьего уровня ''(отрезок 1  — 7 разбивается на отрезки 1  — 6, 6  — 7). Отрезки третьего уровня в свою очередь разбиваются на отрезки ''четвертого уровня'' и  т.  д. Заметим, что на последних уровнях присутствуют только отрезки длины 1  — проекции сторон многоугольника.
 
Рассмотрим одну из частей, на которые диагонали разбивают многоугольник, например, 1  — 2  — 4  — 6. Одна из ее сторон (1  — 6) является отрезком третьего уровня, а остальные  — это все отрезки четвертого уровня, на которые разбивается отрезок 1  — 6. Так устроена любая из частей, как треугольная, так и не треугольная. Таким образом, для того, чтобы найти не треугольную часть, достаточно найти отрезок, который разбивается на три или более отрезков следующего уровня. В нашем примере таких отрезка два: кроме отрезка 1  — 6 есть еще отрезок 7  — 10.
 
{{wikipedia|Число Каталана}}
Перейдем к обсуждению реализации описанной идеи. Будем идти слева направо по горизонтальной прямой, на которую спроецированы все отрезки, и следить за началами и концами отрезков (см. рис.). Обратите внимание: каждый раз, когда мы встречаем начало отрезка, мы опускаемся на один уровень вниз, а когда мы встречаем конец отрезка, мы поднимаемся на один уровень вверх. Таким образом, нас интересует лишь, сколько начал и сколько концов отрезков проектируется в каждую из точек 1, 2, 3, … на горизонтальной оси. (Началом мы считаем вершину с меньшим номером). Определить это можно при считывании входных данных из файла. Пусть <tt>o[i]</tt>  — количество начал, а <tt>c[i]</tt>  — количество концов отрезков, проектирующихся в точку i. Заметим, что в каждую из точек 2, …, ''n''-1 проектируется одно начало и один конец стороны многоугольника, в точку 1 проектируется два начала сторон, а в точку n  — два конца. Напишем соответствующий код:
 
o[1]:=2; for i:=2 to n-1 do o[i]:=1; o[n]:=0;
Строка 47:
end;
 
Что происходит, когда мы встречаем конец отрезка на уровне <tt>level</tt>? Нам хочется узнать, на сколько отрезков был разбит этот отрезок. Если он был разбит лишь на два отрезка, то мы встретили треугольную грань, которая нас не интересует. Если он был отрезком последнего уровня, и не разбивался на отрезки, то он нас также не интересует. Если же этот отрезок был разбит на три или более отрезков следующего уровня, то мы нашли не треугольную грань. Таким образом, нам необходимо хранить количество отрезков, встретившихся нам на уровне <tt>level</tt>  — обозначим это число <tt>l[level]</tt>. О том, как его вычислять, мы поговорим чуть позже. Напишем соответствующий код:
 
if (l[level+1])>2 then begin
Строка 70:
Еще раз подчеркнем: на каждом уровне <tt>level+1</tt> мы считаем количество отрезков, являющихся частями одного и того же отрезка на уровне <tt>level</tt>. Как только отрезок на уровне <tt>level</tt> заканчивается, мы проверяем, на сколько частей он разбит, и если количество этих частей не больше двух, обнуляем <tt>l[level+1]</tt>.
 
Пока мы еще не научились хранить и печатать нужные нам отрезки. Но прервемся ненадолго и оценим, какие ресурсы требует наша программа. Поскольку количество диагоналей не превосходит количества вершин, для хранений начал и концов всех отрезков нам понадобится массив, длина которого пропорциональна количеству вершин многоугольника ''N''. Для заполнения этих массивов нам понадобится порядка ''N'' операций. Таким образом, наш алгоритм работает за линейное относительно ''N'' время и использует память, также пропорциональную ''N''. Мы постараемся, заканчивая реализацию алгоритма, не выходить за указанные ограничения. Итак, нам нужно запоминать встречающиеся вершины. Достаточно запоминать только начала отрезков. Будем на каждом уровне запоминать в массиве <tt>first[level]</tt> первое встретившееся начало отрезка, в массиве <tt>second[level]</tt>  — второе встретившееся начало, а в массиве <tt>next[k]</tt>  — <tt>k</tt>-е встретившееся начало любого уровня:
 
if l[level]=1 then first[level]:=i;
Строка 76:
if l[level]>2 then next[l[level]]:=i;
 
На первый взгляд может показаться странным, что, скажем, 3-е по счету начало на любом уровне мы записываем в один и тот же элемент одного и того же массива, затирая тем самым информацию обо всех ранее найденных третьих началах. Но на самом деле она нам и не нужна. Пусть мы встретили конец некоторого отрезка на уровне <tt>level</tt>, и оказалось, что он разбит не менее чем на три части. Это значит, что каждая из этих частей в свою очередь разбита менее чем на три части (иначе мы бы остановились, дойдя до конца соответствующего отрезка), и каждая из частей этих частей также разбита менее чем на три части и  т.  д. Таким образом, с тех пор как мы встретили третий (четвертый, пятый, …) отрезок на уровне <tt>level+1</tt>, мы более не встречали третьих (четвертых, пятых, …) отрезков, то есть в массиве <tt>next</tt> хранятся номера вершин, служащих началами отрезков именно на уровне <tt>level+1</tt>. Таким образом, мы обходимся всего тремя дополнительными массивами <tt>first</tt>, <tt>second</tt> и <tt>next</tt> длины порядка ''N'' каждый. Теперь несложно вывести вершины многоугольной части, дополнив фрагмент программы, написанный нами выше:
 
if (l[level+1])>2 then begin
Строка 85:
end
 
Осталось объяснить, зачем мы печатаем число ''i''. Дело в том, что кроме начал всех отрезков есть еще одна вершина, которая является вершиной нашей многоугольной части  — самая правая вершина. Это как раз последний встреченный нами конец отрезка, то есть вершина с номером ''i''.
 
Существует множество других алгоритмов, решающих задачу за время ''O(N log N)'' или ''O(N²)'', что удовлетворяет приведенным в задаче ограничениям. Но реализация этих алгоритмов не проще, а зачастую сложнее приведенной в этом разборе реализации линейного алгоритма.
 
== Задача B. Палиндром ==
''Автор разбора  — В.  М.  Гуровиц''
 
Подсчитаем, сколько раз во входном файле встречается каждая буква. Для этого можно воспользоваться массивом:
Строка 134:
 
== Задача C. Представление числа ==
''Автор задачи и разбора  — А.  Ю.  Гусаков''
 
Задача решается применением метода динамического программирования. Прежде чем перейти к описанию идеи решения, введем несколько определений.
 
Будем называть выражение '''C''' ''выражением первого типа'', если оно является числом от 1 до K или если последней операцией при его вычислении является сложение, то есть, '''C '''= '''A + B''', где '''A''' и '''B'''  — некоторые выражения.
 
Будем называть выражение '''C''' ''выражением второго типа'', если оно является числом от 1 до K или если последней операцией при его подсчете является умножение, то есть, '''C '''= '''A * B''', где '''A''' и '''B'''  — некоторые выражения.
Например, (2+3*4)+5*7  — выражение первого типа, <tt>(2+3)*(3+2)</tt>  — выражение второго типа, <tt>1</tt>  — выражение, относящееся как к первому, так и ко второму типу.
 
Теперь обсудим идею решения. Пусть <tt>a[1,m]</tt> равно наименьшей длине выражения первого типа, значение которого равно <tt>m</tt>; <tt>a[2,m]</tt> равно наименьшей длине выражения второго типа, значение которого равно <tt>m</tt>. Легко видеть, что при <tt>m <= K</tt> значения <tt>a[1,m]</tt> и <tt>a[2,m]</tt> равны длине числа <tt>m</tt>.
Пусть теперь <tt>m > K</tt>, и у нас уже вычислены все значения <tt>a[1,1]</tt>, …, <tt>a[1,m-1]</tt>, <tt>a[2,1]</tt>, …, <tt>a[2,m-1]</tt>.
 
Сначала вычислим <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''' меньше или равно, иначе поменяем местами '''A''' и '''B'''.''' '''Таким образом, <tt>a[2,m]=min(a[i1,t]+a[i2,m/t]+1+2*(4-i1-i2))</tt>, где <tt>i1</tt>, <tt>i2</tt>  — 1или 2, а <tt>t<=<math>\sqrt{m}
</math></tt> и <tt>m</tt> делится на <tt>t</tt>.
 
Строка 157:
Теперь мы умеем вычислять значения <tt>a[1,1]</tt>, …, <tt>a[1,N]</tt>, <tt>a[2,1]</tt>, …, <tt>a[2,N]</tt>. Естественно, что искомое выражение является выражением первого или второго типов, поэтому его длина равна <tt>min(a[1,N], a[2,N])</tt>. Осталось только научиться его выводить. Для этого напишем рекурсивную процедуру <tt>Save(last, n)</tt>, которая будет выписывать выражение типа <tt>last</tt>, значением которого является <tt>n</tt>. Во-первых, если <tt>n<=K</tt>, то нужно просто вывести число <tt>cur</tt>. Иначе нужно посмотреть на значение <tt>last</tt>.
 
Если <tt>last=1</tt> (то есть выражение имеет вид '''A+B'''), то сначала выпишем первое слагаемое  — <tt>Save(how[last,n][1],how[last,n][2])</tt>  — затем поставим знак '+' и выпишем второе слагаемое  — <tt>Save(how[last,n][3],n-how[last,n][2])</tt>.
 
Если <tt>last=2</tt> (то есть, имеем дело с произведенем), то нужно действовать аналогично случаю <tt>last=1</tt>, но при этом не забыть, что если какой-то из множителей первого типа, то его надо окружить скобками.
Строка 249:
 
== Задача D. Восстанови многоугольник ==
''Автор задачи и разбора  — В.  М.  Гуровиц''[[Файл:moi_06_1_D1.gif|right|frame|Рис. 1]]
 
Опишем алгоритм восстановления многоугольника по числам в клетках; из этого алгоритма в частности будет следовать, что решение всегда единственное.
Строка 312:
== Задача E. Распредели призы ==
 
''Автор задачи  — Е.  В.  Андреева, авторы разбора  — Е.  В.  Андреева и В.  М.  Гуровиц ''
 
Рассмотрим отдельно три случая.
Строка 352:
 
== Задача F. Монополия ==
''Автор задачи и разбора  — А.  П.  Лахно''
 
Ситуация, рассматриваемая в задаче, описывается неориентированным графом, вершинами которого являются фирмы, а ребра задаются отношением взаимного доверия.
Строка 366:
'''Первое решение'''
 
Основываясь на этих закономерностях, приходим к следующему алгоритму решения задачи. Раскрасим имеющийся граф в два цвета с помощью поиска в глубину: первую вершину каждой компоненты связности красим в белый, все смежные с ней  — в черный, все смежные с ними  — снова в белый и  т.  д. Если при этом в какой-то компоненте связности есть цикл нечетной длины, то возникает коллизия: компоненту связности нельзя раскрасить в два цвета так, чтобы все вершины, смежные с белыми, были черными, а все вершины, смежные с черными,  — белыми.
 
Параллельно с раскраской, для каждой вершины запоминаем номер компоненты связности, в которой она лежит. Для компонент связности, содержащих циклы нечетной длины, помечаем, что их раскрасить не удалось. Кроме того, для каждой компоненты связности запоминаем число белых вершин и число черных вершин в ней.
Строка 378:
Если список вообще не содержит отмеченных вершин из какой-то компоненты, то ни одна вершина этой компоненты никогда не попадет в список отмеченных.
 
Для остальных компонент в первоначальном списке содержатся отмеченные вершины только одного цвета (для каждой компоненты  — своего). Начиная с некоторой итерации, на каждом четном шаге в список отмеченных попадают вершины таких компонент, отмеченных тем же цветом, что и отмеченные вершины в исходном списке, а на нечетных шагах  — вершины противоположного цвета. Единственным исключением здесь компоненты связности, состоящие ровно из одной вершины  — эта вершина в любом случае никогда не попадет в список отмеченных после первого шага.
 
С учетом всего вышесказанного, ответ задачи вычисляется как максимум из трех чисел: количества отмеченных вершин в исходном списке и количеств отмеченных вершин на четных и нечетных шагах с достаточно большим номером, которые в свою очередь несложно вычисляются с помощью ранее посчитанных величин, указанных в начале разбора.
Строка 404:
 
== Задача G. Найди прямую ==
''Автор задачи и разбора  — Б.  О.  Василевский''
 
'''Степенью''' прямой назовем количество данных отрезков, которые она пересекает; концы отрезков будем называть '''вершинами'''.
Строка 414:
2. Итак, можно считать, что искомая прямая должна проходить через какую-либо вершину. Теперь будем вращать эту прямую против часовой стрелки вокруг вершины, через которую она проходит, пока прямая не пройдет через вторую вершину. Аналогично, степень полученной прямой равна степени исходной. И теперь прямая проходит через две различных вершины.
 
На этих идеях основано решение с алгоритмической сложностью O(N³), где N  — количество отрезков: перебираем все пары вершин; для каждой пары считаем степень прямой; через эти вершины проходящей; среди них выбираем прямую с наибольшей степенью. Но такое решение не набирает полного балла.
 
Решение с алгоритмической сложностью O(N² log N) использует только первое рассуждение: искомая прямая проходит через вершину. Таким образом, если для каждой вершины найти прямую наибольшей степени, которая проходит через нее, то выбрав среди всех степеней максимум, получим ответ.
 
Научимся искать прямую с наибольшей степенью, проходящую через вершину P(xp, yp). Любое упоминание прямой теперь подразумевает, что она проходит через P. Сразу договоримся не рассматривать отрезки, проходящие через P, так как они не влияют на поиск прямой максимальной степени. Главное  — не забыть их подсчитать и учесть при вычислении степени прямой.
 
Общая идея такова: будем вращать прямую y = yp вокруг P против часовой стрелки, считая пересечения.
 
'''Ориентированной площадью''' ('''A''', '''B''') пары векторов '''A''' = (x1, y1) и '''B''' = (x2, y2) назовем число, равное x1*y2 − y1*x2. По абсолютно величине она равна площади параллелограмма, у которого в качестве сторон взяты '''A''' и '''B''', отложенные от одной точки. Она равна нулю тогда и только тогда, когда '''A''' и '''B''' коллинеарны. В противном случае знак ('''A''', '''B''') дает нам информацию о направлении кратчайшего поворота от вектора '''A''' к вектору '''B'''.
Если система координат выбрана стандартным образом, то ('''A''', '''B''') больше нуля тогда и только тогда, когда кратчайший поворот  — против часовой стрелки, см.рис.1 (соответственно, ('''A''', '''B''') меньше нуля тогда и только тогда, когда кратчайший поворот  — по часовой стрелке, см. рис. 2).
 
[[Файл:Moi06_1_G_12.gif|center|]]
 
Назовем '''началом''' отрезка XY ту его вершину, которая встретится при вращении нашей прямой раньше остальных точек этого отрезка; '''концом'''  — ту, которая встретится последней. Это можно определить, вычислив знак ориентированной площади S = ('''PX''', '''PY'''): если X  — начало, то S > 0. В случае, если X, Y и P лежат на одной прямой, началом будем считать любую из вершин, концом  — оставшуюся.
 
Рассмотрим для начала более простой случай: по отношению к P все отрезки лежат справа и сверху.
Строка 448:
)
 
Понятно, что после просмотра вершины Q степень всех прямых между PQ и PS (где S  — следующая за Q вершина в отсортированном списке) равна C (любая из этих прямых пересекает все отрезки, которые уже «начались», но еще не «закончились», их ровно C по построению). Среди всех таких значений C надо выбрать наибольшее. В качестве прямой с соответствующей степенью можно брать, к примеру, PQ, как и описано в алгоритме.
 
Сложность общего случая (когда отрезки расположены произвольно) заключается в следующем: пусть мы сравниваем точки как обычно  — по полярному углу. Тогда привычное свойство сравнения «из a <= b, b <= c, следует a <= c» не выполняется, например, для вершин a = (0, 1), b = (1/2, −1/2), c = (-1/2, −1/2), P = (0, 0). Поэтому любая сортировка за время N log N, основанная на таком свойстве, будет сортировать точки неправильно. А ведь именно за счет сортировки за время N log N мы имеем оценку O(N² log N), а не O(N³).
 
Существует несколько способов выйти из этой ситуации, но наиболее простой, на наш взгляд, следующий.
 
Исходная прямая  — по-прежнему y = yp. Разделим отрезки на два типа:
# пересекающие y = yp,
# не пересекающие y = yp.
Идея в том, чтобы перед сортировкой подвергать симметрии относительно P все вершины, лежащие ниже P (не забывая, начало это или конец). Но делать такую симметрию надо аккуратно.
 
Пусть отрезок XY после возможной симметрии его вершин, описанной выше, перешел в отрезок X’Y'. Если ориентированная площадь ('''PX''', '''PY''') отличается по знаку от ориентированной площади ('''PX'''', '''PY''''), то визуально начало и конец «поменялись местами» (мы по-прежнему называем X` началом, если X  — начало и наоборот  — концом, если X  — конец). То есть при вращении наша прямая сначала встретит конец X`Y`, а потом начало (см. рис. 3). В этом случае надо учитывать, что прямые из области 3 (см. рис. 3) тоже пересекают XY (в алгоритме  — шаг 3). Кстати, такое возможно, только если XY  — первого типа.
 
[[Файл:MOI06_1_G_3.gif|center|]]
Строка 465:
С отрезками второго типа таких неудобств не будет.
 
'''Замечание 1. '''Если приступать к сортировке, проделав предварительно лишь описанные преобразования, мы не получим правильного порядка. Пусть, например, P(0, 0), A(-1, 0), B(1, 0), A и B  — начала. Тогда вершины A и B будут считаться равными (подумайте почему). Чтобы избежать этого, можно подвергать симметрии еще и точки, лежащие на y = yp, но левее P. Тогда никакие две вершины не будут лежать с P на одной прямой и одновременно по разные стороны относительно P.
 
'''Замечание 2. '''Чтобы проверить, лежит ли P на отрезке AB, надо сначала убедиться, что все эти три точки лежат на одной прямой. Если это верно, можно посмотреть скалярное произведение векторов PA и PB: если оно меньше или равно 0, то P принадлежит AB (0 может быть, если один из векторов нулевой), в противном случае  — нет.
 
Для каждой точки X через X' будем обозначать следующее: если X ниже P, или X принадлежит y = yp и левее P, то X' симметрична X относительно P. В противном случае X = X`.
Строка 494:
)
 
'''''Шаг 3 (сортировка и поиск прямой с максимальной степенью). '''''Теперь отсортируем полученный список по полярному углу и будем действовать как в простом случае (единственное отличие  — стартовое значение C может быть отлично от нуля).
 
== Задача H. Тупики ==
 
''Автор задачи  — В.  А.  Матюхин, автора разбора  — В.  М.  Гуровиц ''
 
Задача решается моделированием описанного в условии процесса. Будем хранить номера свободных на данный момент тупиков, и список стоящих в тупиках в данный момент электричек (точнее, времена их отправления и номера тупиков, в которых они стоят). Будем читать из файла последовательно информацию о прибывающих электричках. Для каждой прибывающей электрички нам потребуется:
Строка 516:
# удалять тупик с наименьшим номером.
 
В обоих случаях нам требуется реализовать один и тот же набор операций. То есть мы можем использовать структуры данных одного типа. Такая структура данных называется ''очередь с приоритетами''. Для нее реализуются операции Добавить_элемент и Удалить_наименьший. Если вы пишите программы на языке C++, вы можете воспользоваться реализацией очереди с приоритетами из библиотеки STL (priority_queue из библиотеки queue). Поскольку очередь тупиков (Tup) состоит из целых чисел  — номеров тупиков, то ее объявить совсем просто:
 
priority_queue <int, vector<int>, greater<int> > Tup;
Строка 573:
Мы использовали дополнительный массив a для хранения номеров тупиков, в которые прибывают электрички. Мы не можем выводить их сразу, поскольку может оказаться, что по данному расписанию движение организовать нельзя.
 
Как же устроена priority_queue изнутри и насколько быстро выполняются требуемые операции? Для хранения элементов в очереди с приоритетами используется ''куча  — ''бинарное дерево, элементы которого расположены специальным образом. Наименьший элемент находится в вершине дерева, а добавление и удаление элемента в куче выполняются за логарифм от общего числа элементов. Таким образом, наше решение будет иметь сложность порядка ''N'' log (''N+K''). Подробнее об этой структуре данных можно прочитать, например, в книге Т. Кормена и др. «Алгоритмы: построение и анализ». Обратите внимание, что ограничения на количество тупиков и количество электричек таковы, что при использовании вместо кучи массива или списка решение будет иметь сложность ''N''(''N+K''), и не будет работать на больших тестах за указанное время.
 
Существует также решение, использующее только кучу свободных тупиков. Оно использует предварительную совместную сортировку времен прибытия и отправления всех электричек.