Московская олимпиада по информатике - 2005: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 353:
===Задача F. Монополия===
''Автор задачи и разбора - А.П.Лахно''
Ситуация, рассматриваемая в задаче, описывается неориентированным графом, вершинами которого являются фирмы, а ребра задаются отношением взаимного доверия.
Изначально, вершины, соответствующие согласившимся фирмам, отмечены. Далее, на каждой итерации создается новый список отмеченных вершин: в него включаются те и только те вершины, у которых на предыдущем шаге была хотя бы одна отмеченная смежная вершина.
Рассмотрим ключевые закономерности изменения списка отмеченных вершин.
Пусть на некотором шаге имеются две смежные вершины, хотя бы одна из которых отмечена. Тогда после одной итерации отмеченная вершина может «погаснуть», но после второй она обязательно вновь станет отмеченной. Заметим, что эта вершина заведомо будет попадать в список отмеченных через каждые две итерации.
Если же имеются две отмеченные смежные вершины, то они останутся отмеченными после любого числа итераций.
'''Первое решение'''
Основываясь на этих закономерностях, приходим к следующему алгоритму решения задачи. Раскрасим имеющийся граф в два цвета с помощью поиска в глубину: первую вершину каждой компоненты связности красим в белый, все смежные с ней — в черный, все смежные с ними — снова в белый и т.д. Если при этом в какой-то компоненте связности есть цикл нечетной длины, то возникает коллизия: компоненту связности нельзя раскрасить в два цвета так, чтобы все вершины, смежные с белыми, были черными, а все вершины, смежные с черными, — белыми.
Параллельно с раскраской, для каждой вершины запоминаем номер компоненты связности, в которой она лежит. Для компонент связности, содержащих циклы нечетной длины, помечаем, что их раскрасить не удалось. Кроме того, для каждой компоненты связности запоминаем число белых вершин и число черных вершин в ней.
Проходим по первоначальному списку отмеченных вершин.
Если компонента связности, в которой лежит отмеченная вершина, содержит циклы нечетной длины, то, начиная с некоторой итерации, все вершины компоненты будут попадать в список отмеченных на каждом шаге.
Если исходный список отмеченных вершин содержит как белую, так и черную вершину какой-то компоненты связности, то, также как и в предыдущем случае, начиная с некоторой итерации, все вершины компоненты будут попадать в список отмеченных на каждом шаге.
Если список вообще не содержит отмеченных вершин из какой-то компоненты, то ни одна вершина этой компоненты никогда не попадет в список отмеченных.
Для остальных компонент в первоначальном списке содержатся отмеченные вершины только одного цвета (для каждой компоненты — своего). Начиная с некоторой итерации, на каждом четном шаге в список отмеченных попадают вершины таких компонент, отмеченных тем же цветом, что и отмеченные вершины в исходном списке, а на нечетных шагах — вершины противоположного цвета. Единственным исключением здесь компоненты связности, состоящие ровно из одной вершины — эта вершина в любом случае никогда не попадет в список отмеченных после первого шага.
С учетом всего вышесказанного, ответ задачи вычисляется как максимум из трех чисел: количества отмеченных вершин в исходном списке и количеств отмеченных вершин на четных и нечетных шагах с достаточно большим номером, которые в свою очередь несложно вычисляются с помощью ранее посчитанных величин, указанных в начале разбора.
'''Второе решение'''
Приведем вариант решения, несколько менее естественного, но существенно более изящного. Построим граф, вершинами которого являются пары вида (четность итерации, номер фирмы), а ребра соединяют вершины с разной четностью, соответствующие взаимно доверяющим фирмам. Пометим исходно вершины, соответствующие четной итерации и изначально согласившимся фирмам. Запустим теперь из помеченных вершин обход в глубину или ширину. Ответом задачи будет максимум из количества изначально согласившихся фирм и количеств обойденных вершин с четным и нечетным числом итераций соответственно.
Асимптотика обоих решений определяется асимптотикой процедуры обхода графа, т.е. ''O''(''N''+''M'').
В ограничениях задачи было достаточно разумно при отсутствии правильного решения, написать, по крайней мере, решение, моделирующее процесс. При использовании отсечения по времени и аккуратном кодировании такое решение тоже набирало полный балл.
Заметим, что при моделировании, как это ни странно, не достаточно ''N'' итераций. Приведем простой пример: цепочка из пяти вершин, у которой, кроме того, соединены пятая и третья вершины. Изначально отмечена только первая вершина. В данном случае ответ достигается лишь на шестой итерации при пяти вершинах. В общем же случае оптимальное решение будет найдено, не более чем за 2''N'' итераций.
=Пример=
5
1 0 0 0 0
5
1 2
2 3
3 4
4 5
3 5
===Задача G. Найди прямую===
| |||