printРабочее место участника

printЗадачи

836. Ломаные

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
В первом примере ломаные такие: (1 3), (1 2 3), (1 2 4 3), (1 4 2 3), (1 4 3)
Решения, верно работающие при `N\ ≤\ 100`, будут набирать не менее 70 баллов.
Решения, верно работающие при `N\ ≤\ 10`, будут набирать не менее 30 баллов.
Московская городская олимпиада школьников по информатике, 2008
loading