ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при поддержке
ЦПМ
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 22 23 24 25 26 27 28 >> [Всего задач: 155]      



Задача 98839

Темы:   [ Нерекурсивная генерация объектов ]
[ Числа Каталана ]
Сложность: 4

Перечислить все способы разрезать n-угольник на треугольники, проведя n-2 его диагонали.
Прислать комментарий     Решение


Задача 98840

Тема:   [ Динамическое программирование (прочее) ]
Сложность: 4

(Число разбиений; предлагалась на Всесоюзной олимпиаде по программированию 1988 года) Пусть P(n) — число разбиений целого положительного n на целые положительные слагаемые (без учёта порядка, 1 + 2 и 2 + 1 — одно и то же разбиение). При n = 0 положим P(n) = 1 (единственное разбиение не содержит слагаемых). Построить алгоритм вычисления P(n) для заданного n.
Прислать комментарий     Решение


Задача 98841

Тема:   [ Динамическое программирование (прочее) ]
Сложность: 4

(Счастливые билеты; предлагалась на Всесоюзной олимпиаде по программированию 1989 года.) Последовательность из 2n цифр (каждая цифра от 0 до 9) называется счастливым билетом, если сумма первых n цифр равна сумме последних n цифр. Найти число счастливых последовательностей данной длины.
Прислать комментарий     Решение


Задача 98842

Темы:   [ Нерекурсивная генерация объектов ]
[ Числа Каталана ]
Сложность: 4

Доказать, что n-е число Каталана (количество последовательностей длины  2n из n единиц и n минус единиц, в любом начальном отрезке которых не меньше единиц, чем минус единиц) равно   

Прислать комментарий     Решение

Задача 98851

 [Театр ]
Тема:   [ Вычислительная геометрия (прочее) ]
Сложность: 4

В Театре собираются поставить грандиозную пьесу из двух актов, в которой освещение имеет большое значение. Сцена театра имеет форму выпуклого многоугольника, заданного вершинами в декартовой прямоугольной системе координат. Над сценой находится прожектор, который может перемещаться над ней произвольным образом. Находясь в некоторой точке, прожектор освещает круглую область с центром в этой точке и радиусом R.

В первом акте на сцене лежат квадратные ковры размером HxH, стороны которых параллельны осям координат. Ковры могут частично выходить за пределы сцены. Рассмотрим фигуру, которая состоит из всех точек, находясь в которых, прожектор не освещает ни один из ковров и не освещает территорию вне сцены. Обозначим ее площадь как S1.

Перед вторым актом ковры убирают со сцены. Рассмотрим фигуру, которая состоит из всех точек, находясь в которых прожектор не освещает территорию вне сцены. Ее площадь обозначим как S2.

Задание

По предоставленным входным файлам, каждый из которых описывает сцену и размещение на ней ковров в первом акте, создайте соответствующие им выходные файлы, которые содержат площади S1 и S2 описанных выше фигур.

Входные данные

На вашем диске в каталоге DATA содержатся 10 файлов, которые имеют названия THEATER.D01, THEATER.D02, : , THEATER.D10, следующего формата.

В первой строке заданы числа R, H, N, M. Где R - радиус области, которую освещает прожектор. H - длина стороны квадрата, который представляет ковер. N - количество вершин выпуклого многоугольника, который задает сцену. M - количество ковров. Во второй строке находятся N пар чисел - координаты вершин многоугольника в порядке обхода (по или против часовой стрелки). В третьей строке находятся M пар чисел - координаты центров ковров.

Выходные данные

Создайте 10 выходных файлов THEATER.S01, THEATER.S02, : , THEATER.S10 в вашем каталоге на дискете. Эти файлы должны содержать ответы для соответствующих входных файлов.

Каждый файл должен содержать два числа - целые части площадей S1 и S2. Вам не нужно сдавать программу! Баллы будут начисляться за файлы с правильными ответами.

Пример входных и выходных данных

THEATER.D00

THEATER.S00

0.5 2 4 1

1 1 5 1 5 4 1 4

3 4

3 6

Прислать комментарий     Решение

Страница: << 22 23 24 25 26 27 28 >> [Всего задач: 155]      



© 2004-... МЦНМО (о копирайте)
Пишите нам