задачи (перебор с возвратами)

Задача 1. "Цепочка"

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

Вход

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

Выход

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

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

input.txt	output.txt
7 had uncle take entry nuts you youth	you uncle entry youth had

Задача 2. "Коктейль"

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

Вход

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

Выход

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

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

input.txt	output.txt
7 10 1 7 5 6 6 7 3 1 2 3 5 1 6 3 2 7 2 6 5 2	4

Задача 3. "Насекомые"

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

Вход

В первой строке входного файла INPUT.TXT записаны натуральные числа N – количество насекомых в коллекции и K - количество продаваемых ящиков (0 ≤ N ≤ 10⁶, 0 ≤ K ≤ 25). Во второй строке записаны вместимости ящиков V₁, V₂, …, V_K (1 ≤ V_i ≤ 10⁶). В третьей строке в том же порядке записаны стоимости ящиков P₁, P₂, …, P_K (1 ≤ P_i ≤ 10⁶).

Выход

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

Замечание

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

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

input.txt	output.txt
100 5 75 78 44 47 42 67 3 67 72 17	20

Задача 4. "Dropping the stones"

Вы имеете N камней (1 ≤ N ≤ 10), каждый камень характеризуется весом P_i и стоимостью V_i. Вы должны сбросить эти камни по желобу в один из двух бункеров: A или B. Механизм переключения желоба действует следующим образом. Камни падают в один из бункеров, пока вес содержимого бункера не превысит вес камней в другом бункере не менее, чем на D. Тогда желоб переключается на другой бункер. В начальный момент оба бункера пусты и первый камень падает в бункер A. Задача состоит в том, чтобы собрать камни с максимально возможной стоимостью в бункере B.

Вход

Текстовый файл STONES.IN состоит из N+1 строк. Первая строка содержит N и D, разделенные пробелами. Остальные строки содержат величины P_i и V_i, также разделенные пробелами. Все входные данные, кроме N, целые числа от 0 до 10000.

Выход

Текстовый файл STONES.OUT должен содержать одну строку с суммарной стоимостью камней в бункере B.

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

STONES.IN	STONES.OUT
4 2 2 2 2 2 1 1 1 1	4

Задача 5. ”Волшебник”

Волшебник имеет N магических предметов (1 ≤ N ≤ 30), каждый из которых характеризуется своей ценностью v_i (0 < v_i ≤ 10000). Он может произнести M заклинаний (1 ≤ M ≤ 10), изменяющих ценность имеющихся предметов. Каждое заклинание может быть произнесено не более одного раза. Произнесенное заклинание действует на все имеющиеся предметы. Заклинания делятся на 2 типа. После сотворения заклинания первого типа с номером j стоимость предмета i изменяется в D_ij раз (если 1 < D_ij ≤ 100, абсолютная величина стоимости увеличивается, при 0 ≤ D_ij < 1 уменьшается, при D_ij = 1 остается неизменной). Заклинание второго типа с номером j изменяет стоимость предмета i на R_ij (если R_ij > 0, стоимость увеличивается, при R_ij < 0 - уменьшается, при R_ij = 0 остается неизменной). Волшебник должен с помощью известных ему заклинаний добиться того, чтобы суммарная ценность имеющихся предметов была максимальной.

Вход

Текстовый файл WIZARD.IN содержит M + 2 строки. Первая строка содержит значения N и M. Следующая строка содержит значения v_i (i = 1, ..., N). Наконец, каждая из последних M строк соответствует одному заклинанию. Для заклинания первого типа эта строка содержит символ * и значения D_ij (i = 1, ..., N). Для заклинания второго типа она содержит символ + и значения R_ij (i = 1, ..., N). Данные в строках входного файла разделяются одним или несколькими пробелами.

Выход

Выходные данные помещаются в текстовый файл WIZARD.OUT и содержат две строки. Первая строка содержит получившуюся суммарную стоимость предметов (с точностью до 0.001), вторая - M разделенных одним пробелом чисел t_j (j = 1, ..., M), где t_j = k, если заклинание j было произнесено k-м по счету, и t_j = 0, если заклинание не было произнесено.

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

WIZARD.IN	WIZARD.OUT
4 2 2 2 2 2 * 3 2 1 2 * 0.5 1 1 5	29.000 1 2

Задача 6. "Three operations"

There are two strings: S1, of length k (3 ≤ k ≤ 100), and S2 that is initially empty. The following operations are allowed:

- W: write the first character of string S1 to the end of string S2;

- E: erase the first character of S1;

- R: rotate S1 so that the first character takes the last place, the second character takes a place before the last ..., and the last character becomes the first.

You need to find a sequence of operations that writes a word T to string S2. The length of the word T is less than 11 characters. The length of the sequence must not exceed 150. It's always possible to find the desired sequence.

Input file W_E_R.IN consists of two strings: S1, and T.

Output file W_E_R.OUT contains a sequence of operations separated by a single space.

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

W_E_R.IN	W_E_R.OUT
NOGETISEOROSILE NOSOROG	W E W R E E E W E W E W R W E W

Задача 7. "Jurassic Remains"

Paleontologists in Siberia have recently found a number of fragments of Jurassic period dinosaur skeleton. The paleontologists have decided to forward them to the paleontology museum. Unfortunately, the dinosaur was so huge, that there was no box that the fragments would fit into. Therefore it was decided to split the skeleton fragments into separate bones and forward them to the museum where they would be reassembled. To make reassembling easier, the joints where the bones were detached from each other were marked with special labels. Meanwhile, after packing the fragments, the new bones were found and it was decided to send them together with the main fragments. So the new bones were added to the package and it was sent to the museum. However, when the package arrived to the museum some problems have shown up. First of all, not all labels marking the joints were distinct. That is, labels with letters 'A' to 'Z' were used, and each two joints that had to be connected were marked with the same letter, but there could be several pairs of joints marked with the same letter. Moreover, the same type of labels was used to make some marks on the new bones added to the box. Therefore, there could be bones with marked joints that need not be connected to the other bones. The problem is slightly alleviated by the fact that each bone has at most one joint marked with some particular letter. Your task is to help the museum workers to restore some possible dinosaur skeleton fragments. That is, you have to find such set of bones, that they can be connected to each other, so that the following conditions are true:

* If some joint is connected to the other joint, they are marked with the same label.

* For each bone from the set each joint marked with some label is connected to some other joint.

* The number of bones used is maximal possible.

Note that two bones may be connected using several joints.

Input

The first line of the input file jurassic.in contains N - the number of bones (1 ≤ N ≤ 25). Next N lines contain bones descriptions: each line contains a non-empty sequence of different capital letters, representing labels marking the joints of the corresponding bone.

Output

On the first line of the output file jurassic.out print L - the maximal possible number of bones that could be used to reassemble skeleton fragments. After that output L integer numbers in ascending order - the bones to be used. Bones are numbered starting from one, as they are given in the input file.

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

jurassic.in	jurassic.out
6 ABD EG GE ABE AC BCD	5 1 2 3 5 6

Задача 8. “Hits”

Yesterday, Professor Calamaro read in the news that there were rumors about a possible comeback of Soda Stereo, a famous South American rock group. Although Soda Stereo was a well known group of the late ‘80s, Professor Calamaro had never before heard of them. He decided to go to the nearest music store to buy some of their greatest hits collections. When he arrived to the music store, he found that there were many different greatest hits CDs. Because he didn’t know any of their songs, he decided to spend a certain amount of money to buy a couple of them so that he could listen as many songs as possible. There were two main problems, however: (1) it could be that the money was not enough to buy all the CDs, and (2) many of the CDs have the same songs over and over again. At that moment, he realized that it would be very useful for his purposes to have a program to decide which CDs to buy so that, altogether, he could maximize the number of non-repeated songs with the money budget that he has. If there were two choices that give the highest possible number of songs, he would prefer the cheapest one. Your task is to develop that program.

Input

The first line contains of input file an hits.in integer value B (0 < B < 1000), the Professor’s Calamaro budget, and n (0 < n ≤ 20), the number of CD’s. The n CD descriptions come in the following lines. Each description contains:

• One line with the name of the CD.

• One line with integers m (0 < m < 50), the number of songs, and c (0 < c < 100), the CD´s cost.

• m lines with the titles of the songs (one line, one song).

Names of CDs and song´s titles are character strings of a non–zero length with no more than 80 ASCII characters. There are no two CDs with the same name.

Output

The output file hits.out contains the total number of non–repeated songs professor Calamaro can afford and the total cost of CD’s he must buy.

Sample Input and Output

hits.in	hits.out
10 2 COMFORT Y MUSICA 4 5 En la ciudad Un misil Pasos Entre canibales EL ULTIMO CONCIERTO 3 7 Disco eterno Planeador Pasos	4 5
60 3 TIT1 2 25 1 2 TIT2 3 35 2 1 3 TIT3 4 20 5 2 4 2	5 55

Задача 9. «Шахматный матч»

Входной файл: chess.in

Выходной файл: chess.out

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

Ограничение памяти: 128 М байт

Марк и Максим играют между собой шахматный матч. Вероятность того, что в одной партии победит Марк, равна a/(a+b+c). Вероятность того, что в одной партии победит Максим, равна b/(a+b+c). Соответственно вероятность ничьей равна c/(a+b+c). Мальчики договорились, что матч будет состоять не более, чем из N партий. Но если кто-то из них вырвется вперёд на K очков, то матч сразу заканчивается. Ваша задача – найти ожидаемую продолжительность шахматного матча.

Вход

Во входном файле записаны пять целых чисел – a, b, c, N, K (1 ≤ a, b, c ≤ 10⁶, 3 ≤ N ≤ 10, 1 ≤ K < N).

Выход

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

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

chess.in	chess.out
1 2 1 5 5	5.0000
1 2 1 5 4	4.9336
1 2 1 5 2	3.6133
1 2 1 5 1	1.3320

Пояснение

Победитель партии получает 1 очко, проигравший – 0 очков, если партия заканчивается вничью, то оба игрока получают по ½ очка.