Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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

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

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

 

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

Вход

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

Выход

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

 

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

Вход Выход
f cw  

 


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

 

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

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

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

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

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

 

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

Вход Выход
7 11764 17049 6786 6335 15021 1188 10869 2  

 


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

 

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

Вход

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

Выход

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

 

 

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

Вход Выход
1 1 0  

 

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

 

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

Вход

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

Выход

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

 

 

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

Вход Выход
1 1  

 


 

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

 

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

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

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

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

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

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

 

 

<== предыдущая лекция | следующая лекция ==>
За 2010 г. По трем организациям имеются данные, отраженные в их бухгалтерских балансах. | Задача 2
Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.008 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал