НачалоПодразделы
Другие разделы
| 833. Прямоугольник |
| 834. Витрина |
| 835. Найти и заменить |
Дата и время
17/11/2024 03:24:19
836. Ломаные
Ломаные
Олимпиадные задачи на русском языке| 17/03/2008 | Школьные сборы, дорешивание (2D) |
| 18/03/2008 | Школьные сборы, день 2 (D) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
На окружности отметили `N` точек и пронумеровали их последовательно числами от 1 до `N`.
Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами `i` и `j`.
Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).
Во входном файле записано три натуральных числа `N`, `i`, `j` (`2\ ≤\ N\ ≤\ 2\ 000`, `1\ ≤\ i\ <\ j\ ≤\ N`).
В выходной файл надо вывести остаток от деления количества ломаных на `10^9`.
Пример ввода 1
4 1 3
Пример вывода 1
5
Пример ввода 2
5 1 4
Пример вывода 2
12
Решения, верно работающие при `N\ ≤\ 100`, будут набирать не менее 70 баллов.
Решения, верно работающие при `N\ ≤\ 10`, будут набирать не менее 30 баллов.
Московская городская олимпиада школьников по информатике, 2008
