-
Динамическое программирование
(46 задач)
Алгоритмы на графах
(28 задач)
Вычислительная геометрия
(16 задач)
Комбинаторика
(33 задачи)
Перебор
(14 задач)
Синтаксический разбор
(8 задач)
Структуры данных
(3 задачи)
Длинная арифметика
(7 задач)
Прочие задачи на сообразительность
(7 задач)
Прочие задачи на аккуратную реализацию
(3 задачи)
Сортировка
(15 задач)
Двоичный поиск
(3 задачи)
Фильтр
Задачи
Задача 98677[Казино] |
|
|
|
Имя входного файла: |
casino.in |
|
Имя выходного файла: |
casino.out |
|
Максимальное время работы на одном тесте: |
2 секунды |
|
Максимальный объем используемой памяти: |
64 мегабайта |
|
Максимальная оценка за задачу: |
100 баллов |
Вновь открытое казино предложило оригинальную игру.
В начале игры крупье выставляет в ряд несколько фишек разных цветов. Кроме того, он объявляет, какие последовательности фишек игрок может забирать себе в процессе игры. Далее игрок забирает себе одну из заранее объявленных последовательностей фишек, расположенных подряд. После этого крупье сдвигает оставшиеся фишки, убирая разрыв. Затем игрок снова забирает себе одну из объявленных последовательностей и так далее. Игра продолжается до тех пор, пока игрок может забирать фишки.
Рассмотрим пример. Пусть на столе выставлен ряд фишек rrrgggbbb, и крупье объявил последовательности rg и gb. Игрок, например, может забрать фишки rg, лежащие на третьем и четвёртом местах слева. После этого крупье сдвинет фишки, и на столе получится ряд rrggbbb. Ещё дважды забрав фишки rg, игрок добьётся того, что на столе останутся фишки bbb и игра закончится, так как игроку больше нечего забрать со стола. Игрок мог бы действовать и по-другому - на втором и третьем ходах забрать не последовательности rg, а последовательности gb. Тогда на столе остались бы фишки rrb. Аналогично, игрок мог бы добиться того, чтобы в конце остались ряды rrr или rbb.
После окончания игры полученные фишки игрок меняет на деньги. Цена фишки зависит от её цвета.
Требуется написать программу, определяющую максимальную сумму, которую сможет получить игрок.
Формат входных данных
В первой строке входного файла записано число K (1 ≤ K ≤ 26) - количество цветов фишек. Каждая из следующих K строк начинается со строчной латинской буквы, обозначающей цвет. Далее в той же строке через пробел следует целое число Xi (1 ≤ Xi ≤ 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 |
|
|
Решение |
Задача 64153 |
|
|
Задача "Троллейбусы" Троллейбусы одного маршрута проходят через остановку каждые k (1<=k<=500) минут. Известны времена прихода пассажиров на эту остановку. Если пассажир приходит на остановку в момент прихода троллейбуса, то он успевает уехать на нем. Напишите программу, которая бы определяла, во сколько должен пройти первый троллейбус (это время от 0 до k-1), чтобы: 1) Суммарное время ожидания троллейбуса для всех пассажиров было минимально. 2) Максимальное из времен ожидания троллейбуса было минимально. Входные данные Во входном файле INPUT.TXT записано сначала число k, затем - число N (0<=N<=100000). Затем идет N чисел, задающих времена прихода пассажиров на остановку. Каждое из этих чисел - целое от 0 до 100000. Выходные данные В выходной файл OUTPUT.TXT запишите два числа, являющиеся ответами на первый и второй вопросы задачи соответственно. Если решений несколько, выведите любое из них. Пример файла INPUT.TXT 100 5 0 210 99 551 99 Пример файла OUTPUT.TXT 10 51
|
|
|
Решение |
Задача 64157 |
|
|
Сортировка Во входном файле задано сначала число N (1<=N<=100), а затем N целых чисел, по модулю не превышающих 1000. Выведите N чисел в порядке неубывания. Пример входного файла 5 3 1 2 4 2 Пример выходного файла 1 2 2 3 4
|
|
|
Решение |
Задача 64170 |
|
|
Треугольник Паскаля Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая содержит на одно число больше, чем предыдущая. Первое и последнее из этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него. Входные данные. В файле INPUT.TXT записано одно число N (0<=N<=30). Выходные данные. В файл OUTPUT.TXT вывести N строк треугольника Паскаля. Примечание. Все числа в треугольнике Паскаля при указанных ограничениях входят в Longint. Пример файла INPUT.TXT 8 Пример файла OUTPUT.TXT 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1
|
|
|
Решение |
Задача 76262 |
|
|
|
|
|
Решение |
Страница: << 25 26 27 28 29 30 31 >> [Всего задач: 155]
