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

 

Заметим, что при моделировании, как это ни странно, не достаточно ''N'' итераций. Приведем простой пример: цепочка из пяти вершин, у которой, кроме того, соединены пятая и третья вершины. Изначально отмечена только первая вершина. В данном случае ответ достигается лишь на шестой итерации при пяти вершинах. В общем же случае оптимальное решение будет найдено, не более чем за 2''N'' итераций.

 

'''Пример'''

Существует также решение, использующее только кучу свободных тупиков. Оно использует предварительную совместную сортировку времен прибытия и отправления всех электричек.

 

[[Категория:Информатика]]

[[Категория:Задачи]]