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

Перейти к навигации Перейти к поиску
Нет описания правки
м (→‎Задача H. Тупики: уборка вторых лишних шаблонов "по алфавиту" с помощью AWB)
Спроецируем все стороны и диагонали на горизонтальную прямую и далее будем рассматривать только эти проекции. Заметим, что поскольку стороны и диагонали многоугольника не пересекались, то и их проекции не пересекаются, то есть любые два отрезка-проекции либо не имеют внутренних точек, либо один из отрезков лежит внутри другого. Назовем отрезок 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|Число Каталана}}
 
== Задача E. Распредели призы ==
 
''Автор задачи — Е. В. Андреева, авторы разбора — Е. В. Андреева и В. М. Гуровиц ''
 
 
== Задача H. Тупики ==
 
''Автор задачи — В. А. Матюхин, автора разбора — В. М. Гуровиц ''
 
1

правка

Навигация