Страница: << 328 329 330 331 332 333 334 >> Отображать по:

#3343

Кирпичи (BCD)

Темы: [Динамическое программирование на таблицах]

Имеется бесконечное количество прямоугольных кирпичей размерами \(x_i \times y_i \times z_i\), каждый из которых можно ставить на любую грань (размеры каких-то двух стороны будут размерами основания, размер третьей стороны – высотой). Ваша задача – написать программу, находящую максимальную высоту башни, которую можно построить из этих кирпичей. Один кирпич может быть поставлен на другой, если размеры основания верхнего кирпича строго меньше соответствующих размеров основания нижнего.

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

В первой и единственной строке входного файла записано целое число \(N\) (\(1 \leq N \leq 30\)) – количество типов кирпичей, за которым следуют \(3\times N\) целых чисел (\(N\) троек \(x_i\), \(y_i\), \(z_i\)) описывающих размеры каждого типа кирпичей (\(1 \leq x_i, y_i, z_i \leq 65000\)).

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

Выведите в выходной файл единственное целое число - максимальную высоту башни.

Примеры тестов

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

1 10 20 30

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

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

2 6 8 10 5 5 5

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

#3344

Игра (BCD)

Темы: [Динамическое программирование по подстрокам] [Простые игры]

На листке записано в одну строку \(N\) (\(2 \leq N \leq 100\)) целых положительных чисел. Каждое число не превышает 200. Играют двое. За каждый ход можно зачеркивать крайнее число либо слева, либо справа. Зачеркнутое число добавляется к очкам игрока. \(N\) – четное. Игру начинает первый игрок. Необходимо вывести максимально возможную сумму очков для первого игрока при условии, что противник играет наилучшим образом..

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

В первой строке входного файла содержится одно целое число \(N\) (\(2 \leq N \leq 100\)). В следующих \(N\) строках записан исходный ряд чисел, по одному числу в строке.

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

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

Примеры

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

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

#3345

Проложи дорогу (BC)

Темы: [Алгоритм Дейкстры]

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

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

Первая строка содержит число \(N\) – количество городов в стране (\(1 \leq N \leq 10^4\)). Каждая из последующих \(N\) строк содержит по два целых числа, \(x_i\) и \(y_i\) – координаты соответствующего города (\(|x_i|, |y_i| \leq 10^6\)). Далее содержится число \(M\) – количество особых пар городов (\(0 \leq M \leq min(10^4, N(N-1)/2)\)). Далее в \(M\) строках содержится описание особых дорог, каждое состоит из трех целых чисел: \(u\), \(v\) – пара различных городов, между которыми проходит особая дорога, и \(w\) – стоимости постройки соответствующей дороги (\(1 \leq u, v \leq N\), \(0 \leq w \leq 10^6\)). В последней строке содержатся номера городов А и Б (от 1 до \(N\)).

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

Выведите одно число – искомую минимальную длину. Ваш ответ должен отличаться от правильного не более чем на \(10^{-5}\).

Примеры

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

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

2.0000000000

#3346

Две окружности (AB)

Темы: [Элементарная геометрия]

Пересечь две окружности

На плоскости даны две окружности. Ваша задача – найти все их общие точки.

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

В первой строке входного файла находится число \(K\) (\(1 \leq K \leq 10000\)) – количество пар окружностей. Каждая последующая пара строк описывает пару окружностей: в каждой строке записаны 3 целых числа \(x\), \(y\), \(r\) – координаты центра и радиус соответствующей окружности (\(-1000 \leq x,y \leq 1000\), \(0 < r \leq 1000\)).

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

Для каждой пары окружностей вы должны вывети одну из следующих фраз: “There are no points!!!” – если окружности не пересекаются. “There are only i of them....” – если окружности пересекаются ровно в \(i\) точках. В этом случае последующие \(i\) строк должны содержать координаты точек пересечения в формате \(x\) \(y\). Точки должны быть выведены в лексикографическом порядке (сначала с меньшей координатой \(x\), а при равных \(x\) – сначала с меньшей \(y\)). Координаты следует выводить с 6 знаками после запятой. “I can't count them - too many points :(” – если точек пересечения бесконечно много. Все фразы должны быть выведены без кавычек. Вывод для каждой следующей пары окружностей должен быть отделен от предыдущего одной пустой строкой.

Примеры

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

2
0 0 2
4 0 2
0 0 1
1000 1000 1

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

There are only 1 of them....
2.000000 0.000000

There are no points!!!

#3347

Кратчайший путь (AB)

Темы: [Куча] [Алгоритм Дейкстры]

Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и B.

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

Сеть дорог задана во входном файле следующим образом: первая строка содержит числа \(N\) и \(K\) (\(1 \leq N \leq 100000\), \(0 \leq K \leq 300000\)), где \(K\) – количество дорог. Каждая из следующих \(K\) строк содержит описание дороги с двусторонним движением – три целых числа \(a_i\), \(b_i\) и \(l_i\) (\(1 \leq a_i,b_i \leq N\), \(1 \leq l_i \leq 10^6\)). Это означает, что имеется дорога длины \(l_i\), которая ведет из города \(a_i\) в город \(b_i\). В последней строке находятся два числа \(А\) и \(В\) – номера городов, между которыми надо посчитать кратчайшее расстояние (\(1 \leq A, B \leq N\))

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

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

Примеры

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

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

Страница: << 328 329 330 331 332 333 334 >> Отображать по:

Выбрано

Отменить

Добавить в контест