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

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

Страница: << 48 49 50 51 52 53 54 >> [Всего задач: 277]      



Задача 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

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

Задача 98852

 [Скалы ]
Тема:   [ Куча ]
Сложность: 4

На планете Олимпия рабочие строят новую дамбу. Часть плоскости, на которой проводятся строительные работы, имеет вид прямоугольника размером 1 x L метров, на котором введены координаты, как показано на рисунке.

Для поднятия ландшафта используют специально разработанные магические импульсаторы. Если магический импульсатор силой H поставить в точку с X-координатой p, то в каждой точке q отрезка [p-H;p] на оси X рельеф поднимается на q-p+H метров по всей его ширине (то есть для произвольного Z от 0 до 1), а в каждой точке q отрезка [p;p+H] рельеф поднимается на H+p-q метров по всей его ширине, в остальных точках ландшафт остается неизменным (см. рисунок).

Во время строительства рабочие время от времени интересуются объёмом части дамбы, находящейся над некоторым прямоугольником.

Задание

Напишите программу ROCKS, которая поможет рабочим в их расчётах.

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

В первой строке входного файла ROCKS.DAT содержатся два целых числа: N - количество операций, которые будут выполнять рабочие (1≤N?100000), и L - длина прямоугольника (1≤L?100000).

В следующих N строках содержатся описания операций: первое число строки - номер операции, где "1" означает, что рабочие собираются поставить магический импульсатор, "2" - рабочие хотят узнать некоторый объём. Если операция имеет код "1", то далее идут два целых числа p и H (0≤p?L; 1≤H?L), то есть импульсатор силой H ставят в позицию p (на оси X). Если операция имеет код "2", то далее идут два целых числа A и B (0≤A<B?L); это означает, что рабочие хотят узнать объём части дамбы, которая находится над прямоугольником от A до B по оси X, и от 0 до 1 по оси Z.

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

Создайте выходной файл ROCKS.SOL, в котором для каждой операции, указанной во входном файле, выведите строку со следующей информацией.

Если операция есть "1", то выведите число "-1" без кавычек. Если операция есть "2", то выведите число, равное объёму части дамбы, которая находится над прямоугольником от A до B по оси X, и от 0 до 1 по оси Z, как показано на рисунке.

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

ROCKS.DAT

ROCKS.SOL

2 13

1 7 5

2 5 9

-1

16

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

Задача 102786

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

В семье программистов родился ребенок. Папа-программист хочет назвать ребенка так, чтобы его имя подходило под шаблон P, а мама-программист настаивает на шаблоне M. Найдите самое короткое имя, удовлетворяющее обоим шаблонам, или сообщите, что такого имени не существует и семья находится на грани развода.

Шаблон представляет собой последовательность букв русского алфавита (буква «ё» не используется) и специальных символов, которые имеют следующие значения: 
? любая буква 
* любое (возможно нулевое) число букв 
[P]  любая буква из диапазона P
[!P] любая буква не из диапазона P
{n} предыдущий символ, повторенный ровно n раз
{n;}  предыдущий символ, повторенный не менее n раз 
{n;m} предыдущий символ, повторенный от n до m раз 
@  предыдущий символ, повторенный не менее одного раза

При этом 0 ≤ n ≤ m ≤ 10. Диапазон задается перечислением через запятуюсимволов и интервалов символов. Интервал символов записывается в виде a-b, что означает любую букву, расположенную в алфавите между a и b включительно.
Символы могут комбинироваться. Например, запись [а,о,е,у,и,ы,э-я]@ означает произвольную непустую последовательность гласных (необязательно повторяющихся). Запрещается записывать подряд фигурные
скобки и символы @.

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

В первой строке входного файла записан шаблон папы, а во второй – шаблон мамы. Длина каждого шаблона не превосходит 80 символов.

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

Выведите в выходной файла кратчайшее имя ребенка, удовлетворяющее обоим шаблонам, если такое имя существует. Имя ребенка должно состоять из букв русского алфавита. Большие и маленькие буквы не различаются. В случае нескольких возможных имен требуется вывести первое по алфавиту. Если искомого имени не существует, выведите сообщение «NO SOLUTION».

Пример входного файла

?ик*т[а-о][л-р]*
В??тор*

Пример выходного файла

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


Задача 102787

 [Жадный калькулятор ]
Темы:   [ Динамическое программирование (прочее) ]
[ Длинная арифметика как инструмент ]
Сложность: 4

Задано алгебраическое выражение, составленное из неотрицательных вещественных чисел и знаков операций +, - и ?. Требуется так расставить в этом выражении скобки, чтобы его значение стало максимально возможным.

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

Исходное выражение длиной не более 250 символов записано в первой строке входного файла. Выражение содержит не более 50 чисел, каждое из которых лежит в диапазоне от 0 до 106 . Пробелы внутри чисел не допускаются.

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

Выведите в первую строку выходного файла максимально возможное после расстановки скобок значение выражения, а во вторую строку – само это выражение (если вариантов несколько, нужно выдать любой из них). 

Пример входного файла

1+2 - 3.0*4

Пример выходного файла

0
((1+2)-3)*4
Прислать комментарий     Решение


Задача 102789

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

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

Известно, что сложение двух чисел занимает время p, а умножение – время q. Время, необходимое для вычисления сложного выражения AoB, равно времени, затрачиваемому на выполнение операции o, плюс максимальное из двух чисел – времени вычисления подвыражения A и времени вычисления подвыражения B. Время вычисления операнда полагаем равным нулю. Требуется написать программу, которая: 
    1. Определяет время, необходимое для вычисления заданного выражения на многопроцессорной машине. 
    2. Находит эквивалентное заданному арифметическое выражение с минимальным временем вычисления и само это время.

Выражения называется эквивалентными, если одно из них можно получить из другого последовательностью следующих преобразований:
    x + y → y + x ,                    x * y → y * x                    (коммутативный закон),
    x + (y + z) → (x + y) + z ,    x * (y * z) → (x * y) * z    (ассоциативный закон).

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

В первой строке входного файла содержатся два целых числа p и q (1 ≤ p,q ≤ 1000), во второй – арифметическое выражение длиной не более 200 символов.

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

Первая строка выходного файла должна содержать ответ на первый пункт задачи. Во вторую строку выведите эквивалентное заданному выражение с минимальным временем вычисления, а в третью – само это время.

Пример входного файла

1 1
((a+(b+(c+d)))*e)*f

Пример выходного файла

5
((a+b)+(c+d))*(e*f)
3
Прислать комментарий     Решение


Страница: << 48 49 50 51 52 53 54 >> [Всего задач: 277]      



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