Богатов Р.Н., 2009
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
В результате конфликта среди владельцев маршрутных автобусов пришлось разбить некий маршрут на отрезки. При этом начальные и конечные остановки отрезков не совпадают, а являются соседними. Например, если в маршруте 10 остановок, то разбиение на три отрезка может выглядеть так: 1-4, 5-6, 7-10. Но разбить маршрут хотелось бы с минимальной потерей прибыли. Водители не знают, кто из пассажиров куда ездит, но имеют статистику о том, сколько человек на какой остановке вышло и сколько зашло.
Для упрощения задачи допустим, что маршрут однонаправленный, а усреднённая статистика приведена к целым числам. Также условимся, что все пассажиры не согласны на пересадки (если человек ездил, например, от 2-й остановки до 5-й, а предпринято разбиение, описанное выше, то как клиент такой пассажир будет потерян).
Требуется найти такое разбиение маршрута из N остановок на M отрезков, при котором потери клиентов будут минимальными. Если таких разбиений несколько, вывести любое из них.
Ввод: первая строка содержит M, вторая – N, и далее следует N строк с парами чисел Ki и Li – количеством людей, вышедших и вошедших на i-й остановке, i = 1, 2, ..., N; Ki и Li записаны через пробел.
Вывод: M − 1 строка с упорядоченными по возрастанию номерами конечных остановок отрезков, за исключением последнего (в примере выше в ответ войдут остановки 4 и 6).
Ограничения: 2 ≤ M ≤ 100; 2 ≤ N ≤ 100; M ≤ N; Ki и Li – неотрицательные целые; Li ≤ 40; к первой остановке автобус приходит пустой, а на последней остановке выходят все.
Примечание. Условия задачи допускают разбиение на отрезки нулевой длины (у которых начальная и конечная остановка совпадают). Такие решения тоже имеют практический смысл. Например, маршрут из 10 остановок может быть разбит на 4 отрезка так: 1-4, 5-5, 6-8, 9-10 (тогда в ответ войдут: 4, 5, 8).
Пример с правильным ответом:
| Ввод | Вывод |
| 3 6 0 26 7 10 11 5 1 10 15 0 17 0 |
3 5 |
Богатов Р.Н., Щербинина Т.А., 2009
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Имеется две флэшки и множество файлов с общим объёмом в точности равным объёму флэшек. Требуется разместить все файлы на флэшках, для чего необходимо разделить их на две части.
Объём первой флэшки – 8192 Мб, второй – 512 Мб. Размеры файлов кратны целому числу мегабайт. Исходными данными является таблица размеров файлов и количества файлов с одинаковым размером. Ответом является такая же таблица с параметрами файлов, отобранных для первой флэшки.
Ввод: первая строка содержит N – количество строк таблицы; далее следуют N строк с парами чисел V и C, записанными через пробел, где V – размер файлов, C – количество файлов размера V.
Вывод: строка "Impossible" (без кавычек), если разбиение файлов невозможно, либо необходимое количество строк с парами чисел V и C, описывающими файлы для первой флэшки (число строк в начале файла выводить не нужно).
Ограничения: 1 ≤ N ≤ 32; 1 ≤ V ≤ 8704; 1 ≤ C ≤ 8704; все V в таблице попарно различны; суммарный размер файлов равен 8704; суммарный размер файлов в ответе должен быть равен 8192.
| Ввод | Вывод |
| 5 1 500 2 400 3 300 4 201 100 57 |
1
346 2 282 3 266 4 196 100 57 |
Ершов Е.С., 2009
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/58800/65000/65000 Кб.
Дан граф с N вершинами, представленный в виде матрицы смежности. Назовём пучком подмножество вершин, обладающее следующими свойствами:- каждая из вершин имеет по одной входящей и одной исходящей
дуге;
- все входящие дуги исходят из одной и той же вершины, не принадлежащей
пучку (из истока пучка);
- все исходящие дуги входят в одну и ту же вершину пучка, также не
принадлежащую пучку (в сток пучка);
- сток и исток пучка — разные вершины.
При обнаружении две параллельные вершины пучка "стягиваются" в одну как показано на рисунке:
Требуется найти общее количество возможных "стягиваний" вершин в данном графе.
Ввод: в первой строке N, затем N строк матрицы смежности, содержащих нули и единицы через пробел. Элемент матрицы смежности aij равен 1, если i-я и j-я вершины соединены дугой, исходящей из вершины i, иначе 0.
Вывод: искомое число возможных "стягиваний".
Ограничения: 4 ≤ N ≤ 100.
| Ввод | Вывод |
| 4 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 |
1 |
Богатов Р.Н., 2009
Лимит времени 7000/14000/14000/14000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Известна детская игра превращения слов, когда за один ход можно менять только одну букву. Так, например, из слова «миг» можно легко получить «час», а из «муха» можно получить «слон»!
Допустим, Вы располагаете словарём, содержащим все существующие трёхбуквенные слова. Определите, возможно ли такое преобразование между двумя заданными словами, и если возможно, то какое потребуется минимальное количество промежуточных слов. Например, если для слов «миг» и «час» самым коротким преобразованием окажется «миг»-«маг»-«май»-«чай»-«час», то ответом будет 3. Если слова преобразуются за один ход, ответом является 0.
Дополнительно условимся, что никакое слово не содержит двух одинаковых букв. Для удобства ввода-вывода все слова в словаре записаны строчными латинскими буквами. Максимально возможное число слов в таком словаре – 15600. Начальное и конечное слово обязательно присутствуют в словаре.
Ввод: первые две строки содержат начальное и конечное слово; третья строка – количество слов в словаре N, и далее следуют N строк со словами словаря; 2 ≤ N ≤ 15600.
Вывод: количество промежуточных слов или "No solution!" (без кавычек), если преобразование невозможно.
| Ввод | Вывод |
| dar tip 8 var dar tor par pir vor tip tir |
3 |
Богатов Р.Н., 2009
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Известно, что множество k-битных чисел при чётных k можно разместить в матрице размерности 2N x 2N, N=k/2, так, чтобы любые два соседних элемента по вертикали и горизонтали отличались в двоичном представлении не более чем в одном бите. При этом «соседство» обладает свойством тороидальности: у граничных элементов (крайних строк и столбцов) соседними являются противоположные граничные элементы (например, на рисунке для элемента с двоичным представлением 1001 соседом слева будет являться элемент последнего столбца той же строки – 1000).
На рисунке изображён пример такой матрицы при N=2. Элементы приведены в двоичном представлении.
Требуется построить такую матрицу для заданного N.
Ввод: N.
Вывод: 22N элементов искомой матрицы, выведенные построчно через пробел.
Ограничения: 2 ≤ N ≤ 8.
| Ввод | Вывод |
| 2 | 13
15 14 12 9 11 10 8 1 3 2 0 5 7 6 4 |