35 , решение в паскале
вновь открытое казино предложило оригинальную игру.
в начале игры крупье выставляет в ряд несколько фишек разных цветов. кроме того, он объявляет, какие последовательности фишек игрок может забирать себе в процессе игры. далее игрок забирает себе одну из заранее объявленных последовательностей фишек, расположенных подряд. после этого крупье сдвигает оставшиеся фишки, убирая разрыв. затем игрок снова забирает себе одну из объявленных последовательностей и так далее. игра продолжается до тех пор, пока игрок может забирать фишки.
рассмотрим пример. пусть на столе выставлен ряд фишек 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 символов, и все они непустые.
выходные данные
выведите единственное целое число — максимальную сумму денег, которую может получить игрок.
AutoHotkey позволяет автоматизировать задачи пользователя Windows таким образом, какой невозможен или затруднён в других языках программирования. Кроме того, этот язык компактен, самодостаточен и работает на всех версиях Windows «прямо из коробки».
//Обьявляем дополнительные переменные и главный массив, а также два дополнительных - они будут "половинками".
var
a, b, c: array [1..100] of longint;
i, min, n, j, t: longint;
begin
//Читаем количество элементов в нашем массиве.
readln(n);
//Читаем массив.
for i := 1 to n do read(a[i]);
//Заполняем первую "половинку".
for i := 1 to n div 2 do b[i] := a[i];
//Заполняем вторую "половинку". Но раз это уже вторая "половинка" главного массива, то и
//цикл теперь должен начинаться со второй части массива, а заканчиваться уже в его конце.
for i := n div 2 + 1 to n do c[i - n div 2] := a[i];
//Теперь отсортируем первую "половинку" методом выбора. Идея этого метода
//основывается на том, что мы ищем минимальный среди неотсортированных элемент,
//а затем аем его с тем, который стоит сразу после отсортированных.
for i := 1 to (n - 1) div 2 do
begin
min := i;
for j := i + 1 to n div 2 do
if b[min] > b[j] then
min := j;
if min <> i then begin
t := b[i];
b[i] := b[min];
b[min] := t;
end;
end;
//Затем вторую точно также, только стоит обратить внимание на сравнения.
//Так как надо отсортировать по убыванию, то теперь сравнение перед "swap"-ом
//будет другим.
for i := 1 to (n - 1) div 2 do
begin
min := i;
for j := i + 1 to n div 2 do
if c[min] < c[j] then
min := j;
if min <> i then begin
t := c[i];
c[i] := c[min];
c[min] := t;
end;
end;
//А теперь по очереди выводим готовые "половинки", не забывая ставить
//пробел после вывода каждого элемента.
for i := 1 to n div 2 do write(b[i], ' ');
for i := 1 to n - n div 2 do write(c[i], ' ');
end.