Пример входа и выхода

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

Задача 1. Задача о НОП

Даны две символьные последовательности. Найти их наибольшую общую подпоследовательность.

Вход

В текстовом файле INPUT.TXT записаны две символьные строки длиной не более 200 символов каждая.

Выход

В первой строке текстового файла OUTPUT.TXT вывести длину НОП, во второй строке вывести саму НОП.

Пример входа и выхода

Задача 2. " Игроки" (Отборочный тур Всероссийской студенческой олимпиады по информатике. 2004 год. Задача 2)

Фишки разложили в стопки (в разных стопках может быть различное количество фишек), а стопки расположили на столе в ряд слева направо. Два игрока по очереди делают ходы: один из игроков берет слева несколько стопок, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более К стопок. Игра заканчивается, когда стопок не остается. Требуется написать программу для вычисления, какое максимальное число фишек может накопить первый участник после окончания игры, если второй тоже старается ходить так, чтобы получить как можно больше фишек.

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

Входной файл INPUT.TXT состоит из одной строки, в которой записаны: число стопок N (1 ≤ N ≤ 180), за ним идут N чисел, задающих количество фишек в стопках слева направо (количество фишек в стопке - не менее 1 и не более 20000), а затем число К, ограничивающее количество стопок, которые первый игрок может взять на первом ходе (1 ≤ К ≤ 80). Все числа в строке разделены пробелом.

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

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

Пример входа и выхода

Задача 3. " Признак делимости на K" (Личный Зимний турнир 2004 года. Задача A)

Найдите количество чисел, делящихся на K, в двоичной записи которых ровно N единиц и ровно M значащих нулей.

Вход

Входной файл INPUT.TXT состоит из одной строки, в которой записаны три целых числа K, N и M (1 ≤ K ≤ 100, 1 ≤ N ≤ 30, 0 ≤ M ≤ 30- N).

Выход

В выходной файл OUTPUT.TXT следует записать найденное количество чисел.

Пример входа и выхода

Задача 4. " Роман" (Областная олимпиада 1998г. Задача B)

В романе N глав (N ≤ 100). В i -ой главе A_i страниц. Требуется издать роман в K томах (1 < K < N) так, чтобы объем самого толстого тома был минимален. Делить и переставлять главы нельзя.

Вход

В текстовом файле INPUT.TXT записаны целые числа N, K, A₁, A₂,..., A_N в указанном порядке. Количество страниц в романе не превосходит 2, 000, 000, 000.

Выход

В текстовый файл OUTPUT.TXT записать количество страниц в самом толстом томе.

Пример входа и выхода

Задача 5. “STRINGS” (Олимпиада БГУ. 2003 год)

Последовательной подстрокой некоторой строки A назовем строку B, удовлетворяющую условиям:

- для каждого символа b из строки B существует соответствующий ему символ f(b) в строке A;

- если элемент b₁ строки B стоит перед элементом b₂ этой же строки, то элемент f(b₁) стоит в строке A перед элементом f(b₂).

Так, строка bas является последовательной подстрокой строки bananas, а строка abas - не является. Требуется ввести две непустых строки S1 и S2 и определить минимальную по длине последовательную подстроку строки S1, которая не является последовательной подстрокой S2.

Входные данные находятся в текстовом файле STRINGS.IN и содержат две строки S1 и S2. Строки содержат только маленькие буквы латинского алфавита; суммарная длина строк не превосходит 500.

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