ЛАБОРАТОРНАЯ №3
Динамическое программирование
| Input file name: | input.txt |
| Output file name: | output.txt |
| Time limit (per test case): | 1 sec |
| Memory limit (per test case): | 64 MB |
| Score: | 100 points |
A. Взрывоопасность
На одном из секретных заводов осуществляется обработка радиоактивных материалов, в результате которой образуются радиоактивные отходы двух типов: типа А (особо опасные) и типа Б (неопасные). Все отходы упаковываются в специальные прямоугольные контейнеры одинаковых размеров, после чего эти контейнеры укладываются в стопку один над другим для сохранения. Стопка является взрывоопасной, если в ней соседствуют два ящика с отходами типа А.
Требуется написать программу, которая подсчитывает количество возможных вариантов формирования невзрывоопасной стопки из заданного общего числа контейнеров N.
Входные данные: Во входном файле содержится единственное число N (1£ N £81).
Выходные данные: В выходной файл необходимо вывести искомое число вариантов.
| input.txt | output.txt |
B. Сумма
Даны N целых чисел. Найти местоположение подпоследовательности подряд идущих чисел с максимальной суммой.
Формат входных данных
Во входном файле в первой строке записано число N — количество чисел (1≤ N ≤10000). Во второй строке заданы N целых чисел. Каждое из этих чисел не превышает 256.
Формат выходных данных
В выходной файл выведите два числа — номера первого и последнего элементов найденной подпоследовательности.
Примеры
| input.txt | output.txt |
| 0 2 0 4 5 -12 7 -4 9 | 7 9 |
C. Возрастающая последовательность
Даны N целых чисел. В заданной последовательности чисел найти возрастающую последовательность максимальной длины.
Формат входных данных
Во входном файле в первой строке записано число N — количество чисел (1≤ N ≤10000). Во второй строке заданы N целых чисел.
Формат выходных данных
В первой строке выходного файла выведите одно число — количество элементов в полученной возрастающей последовательности, во второй элементы полученной возрастающей последовательности. Если их несколько, напечатать любую из них
Пример
| input.txt | output.txt |
| 12 1 2 4 3 0 5 1 7 | 1 2 4 5 7 |
D. Палиндромы
Не пустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть задана строка, в которой записано слово S, состоящее из N (N≤60) прописных букв латинского алфавита. Путем вычеркивания из этого слова некоторого набора символов, можно получить строку, которая будет называться палиндромом.Требуется написать программу, с помощью которой можно определить, сколько существует способов вычеркивания из заданного слова некоторого (возможно пустого) набора символов, чтобы образованная таким образом строка называлась палиндромом. Способы, отличающиеся порядком вычеркивания символов, считаются одинаковыми.Пример
| input.txt | output.txt |
| BAOBAB |
Индивидуальные задания
Копилка
Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность Pi и вес Wi одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
Ограничения: 1 <= E <= F <= 10 000, 1 <= N <= 500, 1 <= Pi <= 50 000, 1 <= Wi <= 10 000, все числа целые, время 2 с.
Формат выходного файла
Ввод из файла input.txt. В первой строке находятся числа E и F, во второй - число N, в следующих N строках - по два числа, Pi и Wi.
Формат выходного файла
Вывод в файл output.txt. Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".
Примеры
| input.txt | output.txt |
| 1000 1100 1 1 5 2 | 100 250 |
| 1000 1010 6 3 2 2 | 10 16 |
| 1000 2000 10 3 | This is impossible. |
Задача о рюкзаке
Дано n предметов, каждый из которых характеризуется весом wi и полезностью pi. Необходимо выбрать некоторый набор этих предметов так, чтобы суммарный вес этого набора не превышал W, а суммарная полезность была максимальна.
Ваша задача состоит в том, чтобы написать программу, решающую задачу о рюкзаке.
Формат входного файла
Первая строка входного файла содержит натуральные числа n (1≤ n≤100) и W (1≤ W≤ 109). Каждая из последующих n строк содержит описание одного предмета. Каждое описание состоит из двух чисел: wi — веса предмета и pi — его полезности (1≤ wi,pi ≤109).
Формат выходного файла
В первой строке выходного файла выведите максимальную суммарную полезность. Во второй – номера предметов (в порядке следования в исходных данных), которые были использованы.
Примеры
| input.txt | output.txt |
| 2 10 10 100 9 80 | |
| 5 100 80 1000 50 550 50 550 50 550 50 550 | 2 3 |
| 6 200 80 1000 50 550 50 550 50 550 50 550 100 1100 | 2 3 4 5 |
Очередь
За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя «постояльцев» очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.
Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.
Известно, что на продажу i -му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов — Bi секунд, трех билетов — Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.
Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).
Формат входных данных
Во входном файле записано сначала число N — количество покупателей в очереди (1≤ N ≤5000). Далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются начиная от кассы.
Формат выходных данных
В выходной файл выведите одно число — минимальное время в секундах, за которое могли быть обслужены все покупатели.
Примеры
| input.txt | output.txt |
| 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1 | |
| 3 4 5 1 1 1 |
Восстановление скобок
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется написать программу, которая определит сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.
Технические требования:
Формат входных данных:
Входной текстовый файл содержит шаблон длиной не более 80 символов.
Формат выходных данных:
Выходной файл должен содержать одно число - искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2000000000.
Пример
| input.txt | output.txt |
| ????(? |
5. Космический мусорщик
В околоземном космическом пространстве накопилось много мусора, поэтому ученые сконструировали специальный аппарат – ловушку для космического мусора. Для того, чтобы хорошо собирать мусор, этот аппарат должен двигаться по достаточно сложной траектории, сжигая собранный по пути мусор. Ловушка может передвигаться в пространстве по 6 направлениям: на север (N), на юг (S), на запад (W), на восток (E), вверх (U) и вниз (D). Движением ловушки управляет процессор. Программа движения задается шестью правилами движения, которые соответствуют каждому из указанных направлений. Каждое такое правило представляет собой строку символов из множества {N, S, W, E, U, D}.
Команда ловушки есть пара из символа направления и параметра – целого положительного числа M. При исполнении такой команды ловушка в соответствии со своей программой выполняет следующее. Если параметр больше 1, то она перемещается на один метр в направлении, которое указано в команде, а затем последовательно выполняет команды, заданные правилом для данного направления, с параметром меньше на 1. Если же параметр равен 1, то просто перемещается на один метр в указанном направлении.
Пусть, например, заданы следующие правила:
| Направление | Правило |
| N | N |
| S | NUSDDUSE |
| W | UEWWD |
| E | |
| U | U |
| D | WED |
Тогда при выполнении команды S(3) мусорщик выполнит следующие действия:
1) переместится на 1 метр в направлении S
2) выполнит последовательно команды N(2), U(2), S(2), D(2), D(2), U(2), S(2), E(2).
Если далее проанализировать действия мусорщика при выполнении команд из пункта 2, получим, что в целом он совершит следующие перемещения:
SNNUUSNUSDDUSEDWEDDWEDUUSNUSDDUSEE
По заданной команде определите, какое общее количество перемещений на один метр совершит ловушка при выполнении заданной команды. В приведенном примере это количество равно 34.
Формат входных данных
Первые шесть строк входного файла задают правила для команд с направлением N, S, W, E, U и D соответственно. Каждая строка содержит не более 100 символов (и может быть пустой). Следующая строка содержит команду ловушки: сначала символ из множества {N, S, W, E, U, D}, затем пробел и параметр команды – целое положительное число, не превышающее 100.
Формат выходных данных
Выведите в выходной файл единственное число – количество перемещений, которое совершит ловушка. Гарантируется, что ответ не превышает 109.
Пример
| input.txt | output.txt |
| N NUSDDUSE UEWWD U WED S 3 |
6. Количество цифр. Найти количество цифр n- значных чисел, у которых сумма любых двух соседних цифр является простым числом.
Формат входных данных
В единственной строке задано целое положительное число n (n≤20).
Формат выходных данных
В первой строке вывести ответ
Пример
| input.txt | output.txt |
Покупка билетов
За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя «постояльцев» очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.
Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.
Известно, что на продажу i -му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов — Bi секунд, трех билетов — Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.
Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).
Формат входных данных
Во входном файле записано сначала число N — количество покупателей в очереди (1≤ N ≤5000). Далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются начиная от кассы.
Формат выходных данных
В выходной файл выведите одно число — минимальное время в секундах, за которое могли быть обслужены все покупатели.
Примеры
| input.txt | output.txt |
| 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1 | |
| 3 4 5 1 1 1 |
Гвоздики
На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить какие-то пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
Входные данные
В первой строке входного файла записано число N – количество гвоздиков (1 £ N £ 100). В следующей строке записано N чисел – координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).
Выходные данные
В выходной файл нужно вывести единственное число – минимальную суммарную длину всех ниточек.
Пример
| Input.txt | output.txt |
| 4 10 0 12 2 |
Убывающая последовательность
Даны N целых чисел. В заданной последовательности чисел найти убывающую последовательность максимальной длины.
Формат входных данных
Во входном файле в первой строке записано число N — количество чисел (1≤ N ≤10000). Во второй строке заданы N целых чисел.
Формат выходных данных
В первой строке выходного файла выведите одно число — количество элементов в полученной убывающей последовательности, во второй элементы полученной убывающей последовательности. Если их несколько, напечатать любую из них
Пример
| input.txt | output.txt |
| 12 1 2 4 3 0 5 1 7 | 12 4 3 1 |
10. Две строки. Заданы две символьные строки A и B, не содержащие пробелов. Требуется вычислить, сколькими способами можно получить строку A из строки B, вычеркивая некоторые символы. Например, если строки A и B – Сара и СамаринаИрина соответственно, то искомое число равно 7, для строк abc и aaabbbbccc это число равно 36. Формат входных данных В первой строке задана строка A, во второй строке – B. Формат выходных данных В единственной строке вывести количество способов получения строки A из строки B. Примеры
| input.txt | output.txt |
| СараСамаринаИрина | 7 |
| abcaaabbbbccc | 36 |
Программа «Камни»
{$APPTYPE CONSOLE}
Uses SysUtils;
Type mas=array[0..20,0..100] of integer;
vec=array[0..20] of integer;
Var a:mas; p,w:vec; i, j, n, s, k, WW,Wp:integer;
Procedure Print(s,n:integer);
begin
if a[s,n]=0 then exit
else if a[s-1,n]=a[s,n] then Print(s-1,n)
else begin
Print(s-1,n-w[s]);
write(w[s],' ');
end;
end;
Procedure Kamni;
begin
for n:=0 to WW do a[0,n]:=0;
for s:=1 to k do
begin
for n:=0 to WW do
begin a[s,n]:=a[s-1,n];
if n=w[s] then a[s,n]:=1;
if (n>w[s])and(a[s-1,n-w[s]]=1) then
a[s,n]:=1;
end;
end;
end;
Begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(k,WW);
for i:=1 to k do readln(w[i]);
Kamni;
Wp:=0;
for j:=WW downto 1 do
begin
for i:=1 to n do if a[i,j]=1 then
begin k:=i; Wp:=j; break end;
if Wp>0 then break;
end;
writeln('W=',Wp);
Print(k,Wp);
close(input); close(output);
End.
Программа «Рюкзак»
Type mas=array[0..20,0..100] of integer;
vec=array[0..20] of integer;
Var a:mas; p,w:vec; i, n, s, k, WW:integer;
Procedure Print(s,n:integer);
begin
if a[s,n]=0 then exit
else if a[s-1,n]=a[s,n] then Print(s-1,n)
else begin
Print(s-1,n-w[s]); writeln(s);
end;
end;
Begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(k,WW);
for i:=1 to k do readln(w[i],p[i]);
for n:=0 to WW do a[0,n]:=0;
for s:=1 to k do
begin
for n:=0 to WW do
begin a[s,n]:=a[s-1,n];
if (n>=w[s])and(a[s-1,n-w[s]]+p[s]>a[s,n]) then
a[s,n]:=a[s-1,n-w[s]]+p[s];
end;
end;
writeln('P=',a[k,WW]); Print(k,WW);
End.