Завдання І етапу Всеукраїнської олімпіади з інформатики (11 клас)

Завдання І етапу Всеукраїнської олімпіади з інформатики
2008-2009 н.р.
11 клас
Розв’язки можуть бути представлені мовами: Delphi, FPC, Dev-C++, VisualС++

Повітряні шляхи (airways)

Обмеження за часом: 1с.
Обмеження за об’ємом використаної пам’яті: 64 Мбайт.

Управління Повітрянного Руху вимагає, щоб маршрути авіації бути обмеженим. Ми хочемо дослідити витрати при вимозі, щоб авіація летіла лише в декількох направленнях. Наприклад, ми можемо вимагати, щоб літаки летіли лише на північ, на схід, південь, або на захід.

З’ясувалося, що доцільно поширювати допустимі напрямки порівну. Якщо ми дозволяємо лише n напрямів, то один буде східним а інші будуть рівномірно покривати решту напрямів. Наприклад, для n=3 маємо східний напрямок, на 30º західніше півночі та на 30º західніше півдня. Таким чином, між сусідніми напрямками буде кут 120º.

Повний документ