Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Ход конем - 2#33143

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:

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

Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 15\)).

Выходные данные
Выведите единственное число количество способов добраться конём до правого нижнего угла доски.

Примеры

№	Входные данные	Выходные данные
1	4 4	2
2	7 15	13309

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

✓ 235✗ 392700средняяВойти и решать

Ход конем_1#33142

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить ТОЛЬКО на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз (смотри рисунок).

Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 50\)).

Примеры

№	Входные данные	Выходные данные
1	4 4	2

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

✓ 486✗ 655500лёгкаяВойти и решать

Лесопилка#33135

Недавно на лесопилку, где работает Вася, поступил новый заказ. Для постройки нового дома мэру соседнего города требуется a досок длины x футов и b досок длины y футов.

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

Например, если на лесопилке имеются доски длины 80, а клиенту требуется две доски длины 30 и семь досок длины 20, то достаточно сделать семь распилов: одну доску распилить двумя распилами на доски длины 20, 30 и 30, одну тремя распилами на четыре доски длины 20 и одну двумя распилами на доски длины 20, 20 и 40. Доска длины 40 клиенту не нужна, она останется на лесопилке, остальные доски будут отправлены клиенту.

Входные данные

На вход программы поступают числа a, x, b, y и z. Все числа положительны и не превышают 300, x<=z, y<=z, x!=y.

Выходные данные

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

Ввод	Вывод
2 30 7 20 80	7

Динамическое программирование Остатки

✓ 7✗ 43900средняяВойти и решать

Камни#33133

На столе лежат N камней. За ход игрок может взять:

- 1 или 2 камня, если N делится на 3;

- 1 или 3, если N при делении на 3 дает остаток один;

- 1, 2 или 3, если N при делении на 3 дает остаток два.

Каждый ход можно сделать при наличии достаточного количества камней. Проигрывает тот, кто хода сделать не может.

Входные данные: вводится целое число \(0 < N <= 100\).

Выходные данные: выведите 1 или 2 – номер игрока, который выиграет при правильной игре.

Примеры

№	Входные данные	Выходные данные
1	1	1
2	3	2

Динамическое программирование: один параметр Простые игры

✓ 819✗ 1 030500лёгкаяВойти и решать

Обработка больших данных#33128

В научной лаборатории разрабатывается новая архитектура суперкомпьютера,

позволяющая эффективно обрабатывать большие объемы данных.

Суперкомпьютер имеет 2^k ячеек памяти, пронумерованных от 0 до 2^{k– 1}. Отрезком

[L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R,

включительно.

Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является

корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i.

Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются

отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,

6] и [7, 7].

Ключевой операцией в новой архитектуре является операция STORE, которая за одно

действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного

отрезка.

Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить

на суперкомпьютере программу обработки данных, но перед её запуском необходимо

инициализировать память определенным образом. А именно: первые с1 ячеек памяти

необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее,

последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.

Ученым надо выяснить, какое минимальное количество операций STORE необходимо

выполнить, чтобы проинициализировать память требуемым образом.

Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое

содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для

инициализации памяти достаточно трех операций STORE:

- STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;

- STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];

- STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],

как и требуется.

Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не

является корректным отрезком памяти.

Требуется написать программу, которая по заданному содержимому памяти

определяет минимальное количество операций STORE, которое необходимо выполнить для

инициализации памяти заданным образом.

Формат входных данных

Первая строка входных данных содержит три целых числа: k, n и m (0 ≤ k ≤ 30,1 ≤ n ≤ 10

5, 1 ≤ m ≤ 10⁹).

Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci

и vi (1 ≤ ci ≤ 2^k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2^k).

Формат выходных данных

Требуется вывести одно целое число – минимальное количество операций STORE,

которое необходимо выполнить для инициализации памяти заданным образом.

Ввод	Вывод
3 3 2 1 1 2 2 5 1	3

Динамическое программирование Множества Структуры данных

✓ 0✗ 101 300средняяВойти и решать

Мониторинг труб#33124

Газораспределительная система одного региона устроена следующим образом. Она

содержит n узлов, пронумерованных от 1 до n, некоторые узлы соединены односторонними

трубами. Узел с номером 1 соответствует центральному газохранилищу.

Система узлов описывается числами от p2, p3, …, pn. Для всех i от 2 до n узел с

номером pi соединен односторонней трубой с узлом i, газ по этой трубе передается от узла pi

к узлу i. Известно, что возможно доставить газ по трубам от центрального газохранилища до

любого узла системы (возможно, с использованием промежуточных узлов). В системе

используются трубы различных типов, тип трубы обозначается буквой английского алфавита

от «a» до «z». Труба, соединяющая узел pi с узлом i, имеет тип ci.

Для проверки качества труб используется специальный робот. Он помещается в

систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по

которой он перемещается. Робот может перемещаться по трубам только в том же

направлении, в котором по трубе передается газ. Совершив одно или несколько

перемещений по трубам между узлами, робот извлекается из системы труб.

Каждый запуск робота должен соответствовать одной из m заданных спецификаций,

пронумерованных от 1 до m. Спецификация с номером t представляет собой строку st,

состоящую из строчных букв английского алфавита. Запуск соответствует спецификации st,

если количество перемещений робота по трубам во время запуска совпадает с длиной st, и

для всех j от 1 до длины st на j-м шаге робот перемещается по трубе, тип которой совпадает с

st[j] —символом на позиции j в спецификации.

Если запуск робота соответствует спецификации с номером t, то стоимость этого

запуска составляет wt. Оператору системы необходимо проверить все трубы, для этого

можно запускать робот несколько раз. Каждый раз выбирается спецификация и маршрут

робота по трубам, соответствующие выбранной спецификации. Необходимо проверить все

трубы так, чтобы суммарная стоимость запусков робота для проверки качества труб была

минимальна. Одну и ту же трубу можно проверять несколько раз.

Требуется написать программу, которая по описанию системы труб и списку

спецификаций определяет минимальную суммарную стоимость запусков робота, в

результате которых все трубы будут проверены, а также список необходимых для этого

запусков (по требованию).

Формат входных данных

В первой строке входных данных находятся три целых числа n, m и t — количество

узлов системы труб, количество спецификаций запусков робота и параметр, указывающий,

требуется ли вывести список запусков робота или только их минимальную суммарную

стоимость (1 ≤ n ≤ 500, 1 ≤ m ≤ 10⁵, t равно 0 или 1).

В последующих (n – 1) строках содержится информация о трубах, (i – 1)-я из этих

строк содержит разделенные пробелом значения pi и ci, где pi — целое число, задающее

номер узла, из которого ведет труба в i-й узел, а ci — строчная буква английского алфавита,

задающая тип этой трубы (1 ≤ pi ≤ i – 1).

В последующих m строках содержится информация о спецификациях, i-я из этих

строк содержит разделенные пробелом целое число wi — стоимость запуска робота в

соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита

строку si — саму спецификацию (1 ≤ wi ≤ 10⁹). Суммарная длина строк si не превышает 10⁶.

Формат выходных данных

Первая строка выходных данных должна содержать одно число — минимальную

суммарную стоимость запусков робота, в результате которых все трубы будут проверены.

Если проверить все трубы невозможно, требуется вывести «–1».

Если t = 0, то больше ничего выводить не требуется.

Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний

запусков робота. В этом случае вторая строка выходных данных должна содержать

число k — количество запусков робота, которое необходимо выполнить для проверки труб. В

следующих k строках необходимо вывести по три целых числа ai, bi и ci — номер узла, в

котором начинается запуск, номер узла, в котором заканчивается запуск, и номер

спецификации, которой соответствует запуск.

Если оптимальных способов проверки несколько, требуется вывести любой из них.

Ввод	Вывод
3 3 0 1 a 2 b 3 a 4 b 2 a	6
7 3 1 1 a 2 a 3 b 3 b 1 b 6 b 3 aab 5 b 2 ab	15 4 1 4 1 2 5 3 1 6 2 6 7 2

Пояснение к примеру

Система труб, заданная во втором примере входных данных, и оптимальный способ

проверки всех труб для этого случая приведены на рисунке ниже.

Необходимо обратить внимание на следующие моменты:

- трубу можно проверять несколько раз, так в приведенном примере дважды

проверена труба из узла 2 в узел 3;

- одну и ту же спецификацию разрешается использовать несколько раз, в

приведенном примере вторая спецификация используется дважды, для

проверки труб из узла 1 в узел 6 и из узла 6 в узел 7;

- робот может перемещаться по трубам только в том же направлении, по

которому по трубе передается газ, спецификацию «ab» нельзя использовать

для проверки труб по маршруту 2→1→6, так как робот не может

переместиться из узла 2 в узел 1.

Алгоритмы на графах Деревья Динамическое программирование

1 300средняяВойти и решать

Копилка#33105

Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность P_i и вес W_i одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Входные данные
В первой строке находятся числа E и F (1 <= E <= F <= 10000). Во второй - число N (1<= N <= 500). В следующих N строках - по два числа, P_i и W_i(1 <= P_i <= 50000, 1 <= W_i <= 10000). Все числа целые.

Выходные данные
Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".

Задача о рюкзаке

✓ 218✗ 385800средняяВойти и решать

Сдача - 1#33104

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P₁, P₂, ..., P_N рублей. У продавца есть M банкнот номиналом Q₁, Q₂, ..., Q_M. рублей. Определите, смогут ли они рассчитаться.

Входные данные:
- в первой строке задается сумма S;
- во второй строке - число N;
- в третьей строке - N чисел P₁, P₂, ..., P_N;
- в четвертой строке - число M;
- в пятой строке - M чисел Q₁, Q₂, ..., Q_M.
Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

Выходные данные: если продавец сможет рассчитаться с покупателем, выведите номиналы банкнот, которые покупатель отдает продавцу и которые он получает в качестве сдачи. Выводите число со знаком “+”, если банкноту соответствующего номинала покупатель отдает продавцу и со знаком “-”, если покупатель получает эту банкноту на сдачу. Номиналы банкнот разделяйте пробелом.

Если они не могут рассчитаться, выведите строку Impossible.

Примеры

№	Входные данные	Выходные данные
1	10 3 3 9 14 2 6 2	-2 +9 +3
2	100 3 74 35 8 2 19 6	Impossible

Задача о рюкзаке

✓ 73✗ 1851 000средняяВойти и решать

Гирьки#33088

Дан набор гирь массой m₁, …, m_N. Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?

Входные данные:

- в первой строке вводится натуральное число N, не превышающее 100;

- во второе строке вводятся N натуральных чисел m_i, не превышающих 100.

Выходные данные: выведите YES или NO.

Примеры

№	Входные данные	Выходные данные
1	1 17	NO
2	2 19 19	YES

Задача о рюкзаке

✓ 238✗ 407600лёгкаяВойти и решать

0-1 рюкзак: минимум предметов#33087

Дано N предметов массой m₁, …, m_N. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?

Входные данные:

- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второе строке вводятся N натуральных чисел m_i, не превышающих 100.

Выходные данные: выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.

Примеры

№	Входные данные	Выходные данные
1	1 5968 18	0

Задача о рюкзаке

✓ 371✗ 1 267600лёгкаяВойти и решать

0-1 рюкзак: наибольший вес#33086

Дано N золотых слитков массой m₁, …, m_N. Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую массу золота можно унести в таком рюкзаке?

Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второй строке вводятся N натуральных чисел m_i, не превышающих 100.

Выходные данные: выведите одно целое число - наибольшую возможную массу золота, которую можно унести в данном рюкзаке.

Примеры

№	Входные данные	Выходные данные
1	2 3195 38 41	79

Задача о рюкзаке

✓ 653✗ 996400лёгкаяВойти и решать

Задача о рюкзаке с восстановлением ответа#33081

Дано N предметов массой m₁, …, m_N и стоимостью c₁, …, c_N соответственно.

Ими наполняют рюкзак, который выдерживает вес не более M. Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.

Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второй строке вводятся N натуральных чисел m_i, не превышающих 100;

- в третьей строке вводятся N натуральных чисел с_i, не превышающих 100.

Выходные данные: выведите номера предметов (числа от 1 до N), которые войдут в рюкзак наибольшей стоимости (по одному номеру в строке).

Примеры

№	Входные данные	Выходные данные
1	4 6 2 4 1 2 7 2 5 1	1 3 4

Задача о рюкзаке

✓ 400✗ 846600лёгкаяВойти и решать

Сборка компьютера#31928

Для сборки компьютера необходимо T компонентов различного типа (видеокарта, жесткий диск, монитор и т.д.). В магазине продаются N компонентов. Каждый компонент относится к определенному типу и имеет некоторую стоимость и рейтинг по обзорам в журналах.

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

Первая строка ввода содержит одно целое число – количество типов компонентов T (1 ≤ T ≤ 5). Вторая строка ввода содержит одно целое число – количество компонентов в магазине N (1 ≤ N ≤ 1000). Далее следует N строк, содержащих по три целых числа, разделенных пробелами – стоимость i-го компонента C_i (1 ≤ C_i ≤ 3000), его рейтинг R_i (1 ≤ R_i ≤ 3000) и его тип t_i (1 ≤ t_i ≤ T). Далее следует строка, содержащая одно целое число – бюджет на покупку компьютера B (1 ≤ B ≤ 3000).

Вывести в первой строке одно целое число – максимальный суммарный рейтинг использованных компонент. Во второй строке вывести T целых чисел – i-е число означает номер компонента типа i, выбранного для сборки. Если существует несколько вариантов с максимальным суммарным рейтингом, то из них вывести вариант с минимальной стоимостью, а среди таких вариантов можно вывести любой. Если не существует варианта сборки компьютера в рамках указанного бюджета, то вывести в первой строке одно число –1

Ввод	Вывод
2 5 10 6 1 5 7 1 6 10 2 1 5 1 11 11 2 16	18 2 5

Динамическое программирование

✓ 9✗ 711 100средняяВойти и решать

Игра с пешкой#31781

В левой нижней клетке шахматной доски размера N×N стоит пешка. Двое игроков по очереди двигают её, причём каждый может подвинуть её на одну клетку вверх или на одну клетку вправо. На диагонали доски написаны числа a₁, a₂, …, a_N. Когда пешка попадает на диагональ, игра кончается и выигрыш первого игрока равен значению числа, написанного в клетке с остановившейся пешкой. Напишите программу определения гарантированного выигрыша первого игрока.

3
	1
		4
			1
				5
					9
						2
							6

Входные данные

В первой строке записано число N (1 ≤ N ≤ 100). Во второй строке записаны натуральные числа a₁, a₂, …, a_N (1 ≤ a_i ≤ 100).

Выходные данные

Выведите одно число – выигрыш первого игрока.

Ввод	Вывод
8 3 1 4 1 5 9 2 6	5

Динамическое программирование на таблицах Простые игры

✓ 82✗ 290800средняяВойти и решать

Садовник-художник#30783

Садовник посадил N деревьев в один ряд. После посадки деревьев садовнику нужно их покрасить. В его распоряжении есть краска трех цветов: белая, синяя и оранжевая. Сколько способов покраски деревьев есть у него, если никакие два соседних дерева нельзя красить в одинаковый цвет?

Входные данные

В единственной строке записано одно натуральное число - количество деревьев N (1 ≤ N ≤ 50).

Выходные данные

В единственную строку нужно вывести одно число - количество способов покраски.

Ввод	Вывод
3	12

Динамическое программирование

✓ 91✗ 233500лёгкаяВойти и решать

Максимальная сумма смежных элементов#30767

На вход программы подается натуральное число N, а затем N целых чисел. Необходимо определить максимальную сумму смежных элементов последовательности. N не превышает 1000000, каждый элемент последовательности не превосходит по модулю 100.

Примеры

№	Входные данные	Выходные данные
1	9 -2 1 -3 4 -1 2 1 -5 4	6

Пояснения: для заданной последовательности чисел (-2 1 -3 4 -1 2 1 -5 4) наибольшую сумму можно получить для смежной последовательности элементов: 4 -1 2 1.

Решение на 2 балла начисляются при прохождении программой 50% тестов, 3 балла - при прохождении программой 75% тестов.

Динамическое программирование ЕГЭ - вычислительные задачи

✓ 201✗ 331700средняяВойти и решать

Расстояние Дамерау-Левенштейна#28421

Одной из наиболее распространенных опечаток при наборе текста является перестановка двух соседних символов, например, вместо слова «программа» набрано слово «прогармма». Расстояние Левенштейна не учитывает такие опечатки: при вычислении расстояния Левенштейна одна перестановка будет считаться за два редактирования (например, удаление и вставка символа).

При вычислении расстояния Дамерау-Левенштейна, помимо операций замены, вставки и удаления символа допускается еще операция перестановки двух соседних символов. При этом между переставленными символами нельзя вставлять другие символы.

Определите расстояние Дамерау-Левенштейна для двух данных строк.

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

Выходные данные
Требуется вывести одно число – расстояние Дамерау-Левенштейна для данных строк.

Примеры

№	Входные данные	Выходные данные
1	XABCDE ACBYDF	4

Динамическое программирование по подстрокам

✓ 200✗ 409700средняяВойти и решать

Шаблон с ? и *#28419

Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.

Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблонам, либо выдать сообщение, что такой строки не существует.

Входные данные

Заданные шаблоны записаны в первых двух строках входных данных. Длина каждого шаблона не превосходит 80 символов.

Выходные данные

Выведите строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение "No solution!"

Примеры

№	Входные данные	Выходные данные
1	`AB?` `*BC`	`ABC`

Динамическое программирование

✓ 21✗ 1741 200средняяВойти и решать

Расстояние по Левенштейну#28418

Дана текстовая строка. С ней можно выполнять следующие операции:

Заменить один символ строки на другой символ.
Удалить один произвольный символ.
Вставить произвольный символ в произвольное место строки.

Например, при помощи первой операции из строки "СОК" можно получить строку "СУК", при помощи второй операции - строку "ОК", при помощи третьей операции - строку "СТОК.

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

Определите расстояние Левенштейна для двух данных строк.

Входные данные

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

Выходные данные

Требуется вывести одно число – расстояние Левенштейна для данных строк.

Примеры

№	Входные данные	Выходные данные
1	ABCDEFGH ACDEXGIH	3

Динамическое программирование по подстрокам

✓ 314✗ 483500лёгкаяВойти и решать

Наибольшая общая подпоследовательность с восстановлением ответа#28416

Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.

Входные данные

В первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

В третьей строке записано число M – длина второй последовательности (1 ≤ M ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

Выходные данные

Требуется вывести наибольшую общую подпоследовательность данных последовательностей, через пробел.

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3 3 2 3 1	2 3

Динамическое программирование: последовательности

✓ 332✗ 489500лёгкаяВойти и решать