uzluga.ru
добавить свой файл

Муниципальный этап 2004. Задача 3."Цепочка" (30 баллов)

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

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

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

Дана последовательность английских слов. Вы должны составить из этих слов цепочку наибольшей длины. Для каждой пары соседних слов в цепочке последняя буква предыдущего слова совпадает с первой буквой следующего слова. Например, слова yes see exactly young образуют цепочку длиной четыре.

Вход

В первой строке входного файла записано количество чисел N (1<=N<=16). В следующих N строках записаны слова, состоящие только из маленьких латинских букв. Длина любого слова не превосходит 20 символов.

Выход

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

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

input.txt

output.txt

2

answer

answer




artist




input.txt

output.txt

5

yes

repeat

see

see

exactly

exactly

young

yes




young




input.txt

output.txt

3

eye

eye

eye

eye

eye

eye





Муниципальный этап 2008. Задача C. «Коктейль»

Имя файла: cocktail.dpr | cocktail.pas | cocktail.c | cocktail.cpp | cocktail.bas

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

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

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

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

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


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

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


Вход

В первой строке входного файла записаны натуральные числа Nколичество ингредиентов, имеющихся у Васи и M – количество пар не сочетающихся ингредиентов (1 <= N <= 20, 0 <= M <= N*(N-1)/2). В остальных строках файла записано M пар чисел – номера не сочетающихся ингредиентов.


Выход

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


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

input.txt

output.txt

3 3

1 2 2 3 1 3

1

10 0

10

5 2

4 2 5 1

3



Муниципальный этап 2009. Задача B. «Насекомые»

Имя файла: insects.dpr | insects.pas | insects.c | insects.cpp | insects.bas

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

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

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

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

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


У Васи большая коллекция насекомых. Он давно мечтает о специальных застеклённых ящиках, в которых он мог бы хранить свою коллекцию. И вот, наконец, Вася нашёл на барахолке именно такие ящики! Однако продавец заломил за них несусветную цену. Теперь Васе нужно очень быстро определить, какие из ящиков покупать, чтобы и коллекция в них уместилась, и денег потратить как можно меньше.


Вход

В первой строке входного файла записаны натуральные числа N – количество насекомых в коллекции и K - количество продаваемых ящиков (0 <= N <= 106, 0 <= K <= 25). Во второй строке записаны вместимости ящиков V1, V2, …, VK (1 <= Vi <= 106). В третьей строке в том же порядке записаны стоимости ящиков P1, P2, …, PK (1 <= Pi <= 106).


Выход

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


Замечание

В ящик нельзя помещать более Vi насекомых!


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

input.txt

output.txt

100 3

10 20 60

1 2 3

-1

100 3

100 40 70

1000 500 450

950