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

Задачи

Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 46]

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

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

Задача 102888

[Золотая лихорадка ]

Темы:	[	Динамическое программирование (прочее)	]
Темы:	[	Обход графа в ширину	]

Сложность: 4

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

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

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

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

В третьей строке записано целое число L – количество типов реакций, выполняемых философским камнем (1 ≤ L ≤ 100). Далее идут L описаний этих реакций. Каждое описание реакции состоит из двух строк: первая строка содержит название вещества, которое подвергается превращению, вторая – названия веществ, получающихся в результате реакции.

Выходные данные
Ваша программа должна вывести в выходной файл либо одно целое число – искомое количество граммов золота, либо сообщение «QUANTUM SATIS» (лат. "Сколько нужно"), если Петя может получить любое наперед заданное количество золота.

Пример входного файла
4
свинец золото рога копыта
3
свинец
золото рога копыта
рога
золото копыта
копыта
золото

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

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

Задача 102944

[Отравленный пирог ]

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

Сложность: 4

Для игры «Отравленный пирог» используется прямоугольный пирог, разделенный на M «строк» горизонтальными разрезами и на N «столбцов» – вертикальными. Таким образом, пирог должен быть разбит на M × N клеток, правая нижняя из которых «отравлена». Играют двое игроков, ходы делаются по очереди. Каждый ход заключается в том, что игрок выбирает одну из еще не съеденных клеток пирога и съедает все клетки, расположенные левее и выше выбранной (в том числе и выбранную). Проигрывает тот, кто съедает отравленную клетку.

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

Входные данные
Данные во входном файле расположены в следующем порядке: M, N (1 ≤ M, N ≤ 9), X₁, ..., X_M. Здесь X_i – число оставшихся клеток в i-м снизу горизонтальном ряду. Все числа во входном файле разделяются пробелами и/или символами перевода строки.

Выходные данные
В первую строку выходного файла необходимо вывести количество различных выигрышных ходов К, а в последующие K строк – сами выигрышные ходы.

Каждый ход задается парой чисел (i, j), где i – номер (снизу) горизонтального ряда, а j – номер (справа) вертикального ряда, которому принадлежит выбранная клетка (1 ≤ i ≤ M, 1 ≤ j ≤ N).

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

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

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

Задача 98679

[Сетевая игра]

Темы:	[	Динамическое программирование (прочее)	]
Темы:	[	Теория игр	]

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

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

net.in

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

net.out

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

1 секунда

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

64 мегабайта

Максимальная оценка за задачу:

100 баллов

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

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

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

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

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

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

Координаты всех точек неотрицательны и не превосходят 50.

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

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

Примечание

Максимальная оценка за решение задачи при N ≤ 13 равна 40 баллам.

Пример

net.in	net.out
11 1 1 1 2 2 3 2 4 3 1 3 2 1 2 1 3 1 1 2 1 2 1 2 2 2 1 3 1 1 2 2 2 2 2 3 2 1 3 2 3 2 3 3 3	1 6

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

Решение

Задача 98677

[Казино]

Тема:

[

Двойное динамическое программирование

]

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

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

casino.in

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

casino.out

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

2 секунды

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

64 мегабайта

Максимальная оценка за задачу:

100 баллов

Вновь открытое казино предложило оригинальную игру.

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

Рассмотрим пример. Пусть на столе выставлен ряд фишек rrrgggbbb, и крупье объявил последовательности rg и gb. Игрок, например, может забрать фишки rg, лежащие на третьем и четвёртом местах слева. После этого крупье сдвинет фишки, и на столе получится ряд rrggbbb. Ещё дважды забрав фишки rg, игрок добьётся того, что на столе останутся фишки bbb и игра закончится, так как игроку больше нечего забрать со стола. Игрок мог бы действовать и по-другому - на втором и третьем ходах забрать не последовательности rg, а последовательности gb. Тогда на столе остались бы фишки rrb. Аналогично, игрок мог бы добиться того, чтобы в конце остались ряды rrr или rbb.

После окончания игры полученные фишки игрок меняет на деньги. Цена фишки зависит от её цвета.

Требуется написать программу, определяющую максимальную сумму, которую сможет получить игрок.

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

В первой строке входного файла записано число K (1 ≤ K ≤ 26) - количество цветов фишек. Каждая из следующих K строк начинается со строчной латинской буквы, обозначающей цвет. Далее в той же строке через пробел следует целое число X_i (1 ≤ X_i ≤ 150, i = 1..K) - цена фишки соответствующего цвета.

В (K+2)-ой строке описан ряд фишек, лежащих на столе в начале игры. Ряд задается L строчными латинскими буквами (1 ≤ L ≤ 150), которые обозначают цвета фишек ряда.

В следующей строке содержится число N (1 ≤ N ≤ 150) - количество последовательностей, которые были объявлены крупье. В следующих N строках записаны эти последовательности. Гарантируется, что сумма длин этих N строк не превосходит 150 символов, и все они непустые.

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

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

Пример

casino.in	casino.out
6 a 1 b 4 d 2 x 3 f 1 e 3 fxeeabadd 2 aba ed	16

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

Решение

Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 46]