Задача « Трафареты»
В эти дни только Тюбик сидел дома и писал портреты. Каждому жителю Цветочного города хотелось иметь свой портрет, и они совершенно замучили его своими требованиями. Всем обязательно хотелось быть самыми красивыми. Поскольку всем требовалось одно и то же, Тюбик решил сделать несколько трафаретов в виде круга, на границе которого отмечено несколько точек. После этого Тюбик соединял точки всеми возможными способами с помощью непересекающихся отрезков. Например, для 4 точек ему пришлось сделать 9 различных трафаретов, изображенных на рисунке. Вам необходимо вычислить количество трафаретов, которые придется сделать Тюбику в случае п точек. Формат входного файла input.txt В единственной строке записано целое число п (1 < п< 2500) - количество точек на границе круга. Формат выходного файла output.txt В единственной строке запишите одно число - искомое количество трафаретов, вычисленное по модулю (109 + 9).
| INPUT.TXT |
| 3 |
| OUTPUT.TXT |
| 4 |
| INPUT.TXT |
| 4 |
| OUTPUT.TXT |
| 9 |
Разбор задачи №1 "Трафареты"
Камско-Устьинского муниципального района РТ
Запишем условие задачи более формально. Имеются несколько точек на границе выпуклой фигуры и несколько (может быть ни одного) отрезков с концами в этих точках. Никакие 2 отрезка не имеют общих точек.
Требуется найти количество различных вариантов такого размещения отрезков для данного количества точек. Если требуется найти число вариантов, то это наводит на мысль о том, что следует применить метод динамического программирования, т.е. решить задачу для небольших значений данных и, используя полученные результаты, переходить к большим значениям.
Предположим, что мы знаем решения для всех значений количества точек меньших К и результаты храним в массиве А. Если мы не проведём ни одного отрезка, то количество вариантов не изменится. Значит, для получения А[К] надо прибавить к А[К-1] количество вариантов, в которых отрезок проведен из точки с номером К. Пусть проведён такой отрезок. Он разобьёт фигуру на две выпуклые части на контуре которых расположены точки числом меньше К.
Для них мы имеем количество вариантов в элементах массива с индексами меньшими К. Любая пара этих вариантов даёт новый вариант. Если для одной части число вариантов Х, а для другой У, то всего новых вариантов, который нужно прибавить к прежнему значению Х*У. Для каждого отрезка с началом в точке с номером К найдём это произведение и прибавим в предыдущему значению.
Сначала в одной части будет ноль точек, а в другой К-2 (отрезок соединяет точи №1 и К), затем 2 и К-3 и т.д. до последнего отрезка (от № К до №К-1). Остаётся решить задачу для небольших значений. Если точек 0 или 1, то вариант один - не проведено ни одного отрезка, т.е. А[0]=1 и А[1]=1, значения для остальных находим в цикле "для каждого". Т.к. ответ очень большое число каждый раз находим остаток от деления на число, данное в условии задачи.