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

input.txt	output.txt
4 4 1 2 3 4 1 1 2 4 4 1 1 2 4 2 1 3 2 3 1 2	1 0 1 4

Всероссийская олимпиада школьников. Муниципальный этап

Классы

Задача D. «Строка»

Имя файла с исходным текстом программы: string

Входной файл: input.txt

Выходной файл: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64M байт

Максимальная оценка: 20 баллов

Дана строка, состоящая только из символов “ a ”, “ b ” и “ c ”. С помощью операций «вычеркивание» необходимо получить из неё пустую строку. За одно вычёркивание можно удалить из строки первый символ, или последний символ, или сразу и первый и последний символ, если они одинаковы. Так из строки “ abc ” можно получить за одно вычёркивание строку “ bc ” или строку “ ab ”, а из строки “ abca ” можно получить строку “ bc ”.

Ваша задача – для заданной строки найти минимальное количество вычёркиваний, с помощью которых можно получить пустую строку.

Вход

В первой и единственной строке входного файла записана символьная строка, состоящая только из символов “ a ”, “ b ” и “ c ”. Длина строки не превосходит 1000 символов.

Выход

Запишите в выходной файл найденное минимальное количество вычёркиваний.

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

input.txt	output.txt
aabcbbcba
abcab

Подзадачи

Программа, проходящая все тесты со строками длиной не более 10 символов, набирает 10 баллов.

Всероссийская олимпиада школьников. Муниципальный этап

Классы

Задача E. «Инструменты»

Имя файла с исходным текстом программы: tools

Входной файл: input.txt

Выходной файл: output.txt

Ограничение по времени: 2 секунды

Ограничение по памяти: 64M байт

Максимальная оценка: 20 баллов

Васе срочно потребовались инструменты для мелкого ремонта на даче. К сожалению в магазине не оказалось отдельных инструментов, а только наборы. Причём ни один набор не содержал всех необходимых Васе инструментов. Придётся покупать несколько разных наборов, в которых некоторые инструменты дублируются. Ещё надо иметь в виду, что наборы совсем недёшевы. Поэтому Вася нуждается в вашей помощи. Ему нужен оптимальный план покупки, чтобы все инструменты были куплены, и была потрачена минимальная сумма.

Напишите программу, которая находит множество наборов, включающее все необходимые инструменты, и имеющее минимальную суммарную стоимость.

Вход

В первой строке входного файла записаны целые числа N – количество необходимых инструментов и K – количество имеющихся в продаже наборов инструментов (1 ≤ N ≤ 100, 1 ≤ K ≤ 20). Для простоты все необходимые инструменты пронумерованы натуральными числами от 1 до N. В остальных K строках файла содержатся описания наборов инструментов. Описание каждого набора начинается двумя целыми числами M – количество нужных Васе инструментов в наборе, и P – стоимость набора (0 ≤ M ≤ N, 1 ≤ P ≤ 10000). Далее записано M натуральных чисел от 1 до N.

Выход

Запишите в выходной файл минимальную сумму денег, которую придётся потратить Васе. Если решения нет, запишите в выходной файл число -1 (минус единица).

Дата добавления: 2015-07-08