Каталог по темам

Задачи

Страница: << 25 26 27 28 29 30 31 [Всего задач: 155]

Задача 102789

[Параллельные вычисления ]

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

Сложность: 4

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

Известно, что сложение двух чисел занимает время p, а умножение – время q. Время, необходимое для вычисления сложного выражения A^oB, равно времени, затрачиваемому на выполнение операции ^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

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

Задача 102928

[Ограда сада ]

Темы:	[	Перебор с отсечениями	]
Темы:	[	Выпуклая оболочка	]

Сложность: 4

Где-то в далеком царстве-государстве жил-поживал король. Он унаследовал небольшое собрание редких и весьма ценных деревьев. Для того, чтобы обезопасить свою коллекцию от злоумышленников, король приказал возвести вокруг нее высокий забор. Главный королевский колдун был назначен ответственным за исполнение этого поручения.

Увы! Колдун быстро обнаружил, что единственный подходящий материал для постройки забора – это сами деревья. Другими словами, необходимо срубить некоторые деревья для того, чтобы построить забор вокруг оставшихся. Естественно, чтобы сберечь свою голову, колдун захотел минимизировать стоимость срубленных деревьев. Он поднялся в свою башню и оставался там до тех пор, пока не придумал наилучшее возможное решение.

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

Входные данные
В первой строке входного файла записано целое число N – количество деревьев в королевском лесу (2 ≤ N ≤ 14). Деревья нумеруются
последовательными целыми числами от 1 до N. Каждая из последующих N строк содержит четыре целых числа x_i, y_i, v_i, l_i, описывающих очередное дерево. (x_i, y_i) – это координаты дерева на плоскости, v_i – его стоимость, а l_i – длина забора, который может быть построен из этого дерева. Все числа v_i, l_i, а также абсолютные величины x_i и y_i – целые числа из диапазона [0, 10000]. Считается, что деревья имеют нулевой радиус.

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

Пример входного файла
6
0 0 8 3
1 4 3 2
2 1 7 1
4 1 2 3
3 5 4 6
2 3 9 8

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

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

Задача 98680

[Сталкер]

Темы:	[	Кратчайшие пути в графах	]
Темы:	[	Построение графа	]

Сложность: 5+
Классы: 8,9,10,11

Имя входного файла:

stalker.in

Имя выходного файла:

stalker.out

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

128 мегабайт

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

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

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

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

Формат входных данных

В первой строке входного файла находятся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) - количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад - в здании с номером N.

В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число r_i - количество дорог, обозначенных на i-ой карте. Затем идут r_i строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (r₁+ r₂ + ... + r_K ≤ 300 000).

Формат выходных данных

В выходной файл необходимо вывести одно число - минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число -1.

Примеры

stalker.in	stalker.out		stalker.in	stalker.out
5 3 1 3 4 3 1 2 1 3 2 4 1 4 5	2		5 3 2 3 2 4 5 1 2 1 2 1 3 5 4	-1

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

Решение

Задача 66541

Темы:	[	Теория алгоритмов (прочее)	]
	[	Правильные многогранники (прочее)	]
	[	Раскраски	]
	[	Перебор (прочее)	]

Сложность: 3
Классы: 6

Автор: Евдокимов М.А.

а) Мальвина разбила каждую грань куба 2×2×2 на единичные квадраты и велела Буратино в некоторых квадратах написать крестики, а в остальных нолики так, чтобы каждый квадрат граничил по сторонам с двумя крестиками и двумя ноликами. На рисунке показано, как Буратино выполнил задание (видно только три грани). Докажите, что Буратино ошибся.

б) Помогите Буратино выполнить задание правильно. Достаточно описать хотя бы одну верную расстановку.

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

Задача 73812

Темы:	[	Полуинварианты	]
	[	Процессы и операции	]
	[	Теория алгоритмов (прочее)	]
	[	Графы (прочее)	]

Сложность: 4+
Классы: 7,8,9

Автор: Штейнберг А.М.

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

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

Страница: << 25 26 27 28 29 30 31 [Всего задач: 155]