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

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

Страница: << 2600 2601 2602 2603 2604 2605 2606 >> [Всего задач: 21755]      



Задача 102923

 [Круги ]
Тема:   [ Задачи на полный перебор ]
Сложность: 3+

Задан круг, разделенный на N секторов, и два целых числа M и K. В каждый из секторов круга помещается одно целое число, не меньшее K. Когда секторы заполнены числами, из них можно получать новые числа по следующим правилам:
    взять число из одного сектора;
    взять число, равное сумме двух или более чисел в смежных секторах.
Из новых чисел составляется наибольшая последовательность подряд идущих чисел, начинающаяся с числа M: (M, M+1, M+2, ..., I).

Пример на рисунке показывает, как получить все новые числа от 2 до 21 для приведенных на нем чисел в секторах. Серым цветом выделены суммируемые числа.


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

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

Входной файл содержит три целых числа N, M и K (N ≤ 6, M ≤ 20, 0 ≤ K ≤ 20).

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

Выведите в первую строку выходного файла наибольшее число I для неразрывной последовательности новых чисел от M до I, которая может быть получена из чисел в секторах. Далее выведите все наборы чисел в секторах, из которых можно получить такую последовательность. Каждый набор записывается в отдельную строку выходного файла в виде списка чисел, начинающегося с наименьшего из них (оно может быть не единственным). Числа в списке должны идти в том же порядке, в котором они записаны в секторах круга. Если наименьшее число встречается несколько раз, следует вывести все возможные комбинации. Например, (1 1 2 3), (1 2 3 1), (1 3 2 1) и (1 1 3 2).

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

5
2
1

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

21
1 3 10 2 5
1 5 2 10 3
2 4 9 3 5
2 5 3 9 4
Прислать комментарий     Решение


Задача 102935

 [Пересечение многоугольников ]
Темы:   [ Прямая и отрезок ]
[ Площадь ]
Сложность: 3+

Два многоугольника на плоскости заданы координатами своих вершин. Требуется вычислить площадь пересечения этих многоугольников, то есть сумму площадей тех кусков, которые образуются при их пересечении и принадлежат каждому из них. При этом вы можете предполагать, что: 
    А) Многоугольники выпуклые, а координаты их вершин даны в произвольном порядке.
    Б) Хотя бы один из многоугольников невыпуклый, но известно, что у каждого из многоугольников не более одного угла, большего 180 градусов, а координаты вершин даны в порядке обхода по часовой стрелке.
Ваша программа по входным данным должна сама определить, какой из этих двух случаев имеет место.

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

Первая строка входного файла содержит целое число N – количество вершин в первом многоугольнике (3 ≤ N ≤ 50). Во второй строке записаны координаты этих вершин. Третья и четвертая строки таким же образом задают второй многоугольник. Координаты всех вершин являются целыми числами из диапазона [-32768, 32767].

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

Выведите в выходной файл искомую площадь не менее чем с 6 верными значащими цифрами.

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

3
0 3 0 -3 -3 0
5
-1 1 2 1 1 0 2 -1 -1 -1

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

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


Задача 102936

 [Пересечение окружностей ]
Тема:   [ Круги и окружности ]
Сложность: 3+

На плоскости провели N окружностей. Требуется определить площадь их пересечения.

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

В первой строке входного файла находится целое число N (1 ≤ N ≤ 20). В каждой из последующих N строк записана тройка вещественных чисел, описывающих очередную из окружностей. Первые два числа задают координаты ее центра, третье – радиус.

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

Выведите в выходной файл искомую площадь не менее чем с 6 верными значащими цифрами.

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

2
0 0 1
1 1 1

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

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


Задача 102942

 [Кратчайший путь в квадрате]
Темы:   [ Прямая и отрезок ]
[ Кратчайшие пути в графах ]
Сложность: 3+

Внутрь квадрата с координатами левого нижнего угла (0, 0) и координатами правого верхнего угла (100, 100) поместили N квадратиков, стороны которых параллельны осям координат и имеют длину 5. Никакие два квадратика не имеют общих точек. Необходимо найти кратчайший путь из точки (0, 0) в точку (100, 100), который бы не пересекал ни одного из этих N квадратиков.

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

В первой строке входного файла содержится целое число N (1 ≤ N ≤ 30), в каждой следующих N строк – координаты левого нижнего угла (x, y) очередного из квадратиков (0 ≤ x, y ≤ 95).

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

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

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

5
5 5
5 15
15 10
15 20
90 90

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

0 0
5 10
20 20
95 90
100 100
Прислать комментарий     Решение


Задача 102950

 [Булевы функции ]
Тема:   [ Задачи на полный перебор ]
Сложность: 3+

Булевой функцией называется функция, принимающая одно из логических значений TRUE или FALSE и зависящая от некоторого (быть может, нулевого) количества аргументов, каждый из которых также может принимать любое из значений TRUE или FALSE.

Любая булева функция однозначно задается своей таблицей истинности, в которой для каждого возможного набора значений аргументов указано значение функции. Например, x AND y – булева функция от двух аргументов. Ее таблица истинности выглядит так: 

Если договориться, что наборы значений аргументов в таблице располагаются в лексикографическом порядке, то функция AND однозначно задается третьим столбцом таблицы – строкой 0001. Аналогично, каждой булевой функции от k аргументов можно поставить в соответствие строку из нулей и единиц длины 2k.

Задан набор из N+1 булевой функции (f, f1, f2, ..., fN). Напишите программу, которая определяет, можно ли функцию f выразить через функции f1, f2, ..., fN, и если такие представления возможны, то находит кратчайшее по числу символов среди них.

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

В первой строке входного файла записано целое число N (1 ≤ N ≤ 9). Последующие N+1 строк содержат описания функций f, f1, f2, ..., fN соответственно. Каждая из функций описывается строкой символов так, как указано выше. Число аргументов у функции f будет не более двух, а у остальных функций – не более трех.

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

Первая строка выходного файла должна содержать искомое символьное представление, либо строку «Impossible», если такого представления не
существует. После функции с нулевым числом аргументов скобки не ставятся. Если у функции f один аргумент, то он обозначается x, а если два, то они обозначаются x и y.

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

2
1
1010
0

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

f1(f2,f2)
Прислать комментарий     Решение


Страница: << 2600 2601 2602 2603 2604 2605 2606 >> [Всего задач: 21755]      



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