Замечание. Задача 1. Дискретная задача о рюкзаке

Задача 1. Дискретная задача о рюкзаке

Вход

В первой строке входного файла input.txt записаны целые числа N - количество предметов и W - вместимость рюкзака (1 ≤ N ≤ 25, 1 ≤ W ≤ 10⁶). В следующих N строках записаны пары чисел V_i – объём предмета и P_i – стоимость предмета (1 ≤ V_i, P_i ≤ 10⁶).

Выход

В текстовый файл output.txt записать максимальную суммарную стоимость предметов, которые можно уложить в рюкзак.

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

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

Вход

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

Выход

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

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

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

Вход

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

Выход

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

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

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

Вход

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

Выход

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

Замечание

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

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

(ACM ICPC 2001 Western Subregion. Problem B)

Вы имеете 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.

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

(Олимпиада ФПМИ БГУ. 2002. Задача A)

Волшебник имеет 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, если заклинание не было произнесено.

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

(BSU Programming Contest 2004, Minsk, September 2004)

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.

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

(NEERC - 2003. Problem J)

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.