Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N. В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего.
На каждом столбике Кузнечик может получить или потерять несколько золотых монет (для каждого столбика это число известно). Определите, как нужно прыгать Кузнечику, чтобы собрать наибольшее количество золотых монет. Учитывайте, что Кузнечик не может прыгать назад.
В первой строке вводятся два натуральных числа: N и K (2 ⩽ N, K ⩽ 10000), разделённые пробелом. Во второй строке записаны через пробел N целых числа количество монет, которое Кузнечик получает на каждом столбике, от 2-го до N-1-го. Если это число отрицательное, Кузнечик теряет монеты. Гарантируется, что все числа по модулю не превосходят 10 000.
В первой строке программа должна вывести наибольшее количество монет, которое может собрать Кузнечик. Во второй строке выводится число прыжков Кузнечика, а в третьей строке номера всех столбиков, которые посетил Кузнечик (через пробел в порядке возрастания).
Если правильных ответов несколько, выведите любой из них.
5 3
2 -3 5
7
3
1 2 4 5
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Пусть a1..an — числовая последовательность. Длина последовательности — это количество элементов этой последовательности. Последовательность ai..aik называется подпоследовательностью последовательностиa, если 1 ⩽ i1 < ik ⩽ n. Последовательность a называется возрастающей, если a 1 < a2 < ... < an.
Вам дана последовательность, содержащая n целых чисел. Найдите ее самую длинную возрастающую подпоследовательность.
В первой строке задано одно число n (1 ⩽ n ⩽ 2000) — длина подпоследовательности. В следующей строке заданоnцелых чиселa i (109 ⩽ ai ⩽ 109) — элементы последовательности.
В первой строке выведите числоk— длину наибольшей возрастающей подпоследовательности. В следующей строке выведитеkчисел — саму подпоследовательность.
5
1 3 5 4 2
3
1 3 5
3
1 2 3
3
1 2 3
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.
1 2 3
4 5 6
7 8 9
0
Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня. Поскольку таких номеров может быть очень много, выведите ответ по модулю 109.
Во входном файле записано целое число N (1 ⩽ N ⩽ 100).
Выведите в выходной файл искомое количество телефонных номеров по модулю 109.
1
8
2
16
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дана текстовая строка. С ней можно выполнять следующие операции:
- Заменить один символ строки на другой символ.
- Удалить один произвольный символ.
- Вставить произвольный символ в произвольное место строки.
Например, при помощи первой операции из строки "СОК" можно получить строку "СУК при помощи второй операции - строку "ОК" при помощи третьей операции - строку "СТОК.
Минимальное количество таких операций, при помощи которых можно из одной строки получить другую, называется стоимостью редактирования или расстоянием Левенштейна.
Определите расстояние Левенштейна для двух данных строк.
Программа получает на вход две строки, длина каждой из которых не превосходит 1000 символов, строки состоят только из заглавных латинских букв.
Требуется вывести одно число расстояние Левенштейна для данных строк.
ABCDEFGH
ACDEXGIH
3
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Около Петиного университета недавно открылось новое кафе, в котором действует следующая система скидок: при каждой покупке более чем на 100 рублей покупатель получает купон, дающий право на один бесплатный обед (при покупке на сумму 100 рублей и меньше такой купон покупатель не получает).
Однажды Пете на глаза попался прейскурант на ближайшие n дней. Внимательно его изучив, он решил, что будет обедать в этом кафе все n дней, причем каждый день он будет покупать в кафе ровно один обед. Однако стипендия у Пети небольшая, и поэтому он хочет по максимуму использовать предоставляемую систему скидок так, чтобы его суммарные затраты были минимальны.
Требуется найти минимально возможную суммарную стоимость обедов и номера дней, в которые Пете следует воспользоваться купонами.
В первой строке входного файла записано целое число n (0 ⩽ n ⩽ 100). В каждой из последующих n строк записано одно целое число, обозначающее стоимость обеда в рублях на соответствующий день. Стоимость — неотрицательное целое число, не превосходящее 300.
В первой строке выдайте минимальную возможную суммарную стоимость обедов. Во второй строке выдайте два числа k1 и k2 — количество купонов, которые останутся неиспользованными у Пети после этихnдней и количество использованных им купонов соответственно.
В последующих k2 строках выдайте в возрастающем порядке номера дней, когда Пете следует воспользоваться купонами. Если существует несколько решений с минимальной суммарной стоимостью, то выдайте то из них, в котором значение k1 максимально (на случай, если Петя когда-нибудь ещё решит заглянуть в это кафе). Если таких решений несколько, выведите любое из них.
5
110
40
120
110
60
260
0 2
3
5
3
110
110
110
220
1 1
2
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дана строка, составленная из круглых, квадратных и фигурных скобок. Определите, какое наименьшее количество символов необходимо удалить из этой строки, чтобы оставшиеся символы образовывали правильную скобочную последовательность.
Во входном файле записана строка из круглых, квадратных и фигурных скобок. Длина строки не превосходит 100 символов.
Выведите максимальную длину строки, являющуюся правильной скобочной последовательностью, которую можно получить из исходной строки удалением некоторых символов.
([)]
2
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дана строка, составленная из круглых, квадратных и фигурных скобок. Определите, какое наименьшее количество символов необходимо удалить из этой строки, чтобы оставшиеся символы образовывали правильную скобочную последовательность.
Во входном файле записана строка из круглых, квадратных и фигурных скобок. Длина строки не превосходит 100 символов.
Выведите строку максимальной длины, являющейся правильной скобочной последовательностью, которую можно получить из исходной строки удалением некоторых символов.
([)]
[]
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дан граф, являющийся деревом. Множество вершин графа называетсядопустимым, если никакие две вершины этого множества не соединены ребром.
Рассмотрим все допустимые множества вершин графа. Для каждого такого множества посчитаем количество вершин в нём. Каково максимальное из этих количеств?
Граф в этой задаче задан в видекорневогодерева. В графе выделена вершина — корень дерева.
Для каждой вершины i, не являющейся корнем, задан номер вершины - корневом дереве.
Дерево, заданное таким образом, состоит из рёбер i—pi для всех вершин i, кроме корня.
В первой строке входного файла записано целое число n — количество вершин в графе (1 ⩽ n ⩽ 100). В следующих n строках задан граф. В i-й из этих строк записано целое число pi — номер вершины - предка i-й вершины. Для корня дерева pi = 0, для всех остальных вершин 1 ⩽ pi ⩽n.
Гарантируется, что заданный во входном файле граф является деревом.
В первой строке выходного файла выведите одно число — максимальное количество вершин в допустимом множестве.
5 0 1 1 2 3
3 6 5 6 5 1 0 1
3
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Двудольным графом называется неориентированный граф (V, E), E = {V, V} такой, что его множество вершин V можно разбить на два множества A и B, для которых ... Паросочетанием в двудольном графе называется любой набор его несмежных рёбер, то есть такой набор S from E, что для любых двух рёберe ... Ваша задача — найти максимальное паросочетание в двудольном графе, то есть паросочетание с максимально возможным числом рёбер.
В первой строке записаны два целых числа n и m (1 ⩽ n, m ⩽ 250), где n — число вершин в множестве A, аm — число вершин в B.
Далее следуют n строк с описаниями рёбер — i-я вершина из A описана в (i+1)-й строке файла.
Каждая из этих строк содержит номера вершин из B, соединённых с i-й вершиной A. Гарантируется, что в графе нет кратных ребер. Вершины вAиB нумеруются независимо (с единицы). Список завершается числом 0.
Первая строка выходного файла должна содержать одно целое число l— количество рёбер в максимальном паросочетании. Далее следуют l строк, в каждой из которых должны быть два целых числа uj и vj — концы рёбер паросочетания в A и B соотвественно.
2 2
1 2 0
2 0
2
1 1
2 2
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Продавец аквариумов для кошек хочет объехать n городов, посетив каждый из них ровно один раз. Помогите ему найти кратчайший путь.
Первая строка входного файла содержит натуральное число n (1 ⩽ n ⩽ 13) — количество городов. Следующиеnстрок содержат по n чисел — длины путей между городами.
В i-й строке j-е число — ai,j — это расстояние между городами i и j (0 ⩽ ai,j ⩽ 106, ai,j = aj,i, ai,i= 0).
В первой строке выходного файла выведите длину кратчайшего пути. Во второй строке выведите n чисел — порядок, в котором нужно посетить города.
5
0 183 163 173 181
183 0 165 172 171
163 165 0 189 302
173 172 189 0 167
181 171 302 167 0
666
4 5 2 3 1
Имя входного файла: nice.in
Имя выходного файла: nice.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узор из черных и белых плиток, каждая из которых имеет размер 1x1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника nxm метров.
Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во первых, каждый новый клиент очевидно захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во вторых, этот узор должен быть симпатичным.
Как показало исследование, узор является симпатичным, если в нем нигде не встречается квад- рата 2x2 метра, полностью покрытого плитками одного цвета.
Для составления финансового плана директору необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!
На первой строке входного файла находятся два натуральных числа n и m. 1 ⩽ nxm ⩽ 30.
Выведите в выходной файл единственное число — количество различных симпатичных узоров, которые можно выложить во дворе размера nxm. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением считаются различными.
1 1 2
1 2
4
Имя входного файла: skyscraper.in
Имя выходного файла: skyscraper.out
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Коровы любят соревноваться в беге по лестницам небоскребов. А вниз потом едут на лифте.
Лифт имеет максимальную вместимость w (1 ⩽ w ⩽ 108) фунтов, а корова номер i весит ci (1 ⩽ ci ⩽ w) фунтов.
Помогите Бесси определить минимальное количество спусков лифта, чтобы переместить вниз все n (1 ⩽ n ⩽ 18) коров.
Сумма весов коров в каждом спуске не должна превышать W.
Первая строка содержит два целых числа n и w (1 ⩽ n ⩽ 18, 1 ⩽ w ⩽ 108).
Следующие n строк содержат веса коров: i-я строк содержит целое число ci (1 ⩽ ci ⩽ w).
Первая строка должна содержать число r — минимально количество спусков лифта.
Каждая из следующихrстрок содержит множество коров, которые сейчас спускаются. Строка начинается с количество коров на данном спуске, далее содержатся номера коров.
4 10
5
6
3
7
3
2 1 3
1 2
1 4
Замечание Всего 4 коровы с весами 5 6 3 и 7. Вместимость лифта — 10. Мы можем поместить в лифт корову 3 и любую из оставшихся коров. Но все другие коровы не помещаются даже по две. В решении представленном выше, в первом спуске участвуют коровы 1 и 3, Во втором — корова 2, в третьем — корова 4. Существует несколько правильных решений для данного ввода.