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

Муравьиная ферма#37892

У мальчика Пети есть муравьиная ферма. На ферме есть участок прямоугольной формы, состоящий из NxM квадратов. В правом нижнем квадрате данной области имеется дырка, благодаря которой можно сбежать с фермы. Каждый день очередной муравьишка начинает свой путь с левой верхней клетки. Далее он перемещается в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться он не может), и двигается так до достижения правой нижней клетки. Затем он выбирается наружу. Каждый муравьишка двигается своим уникальным путем (т.е. никакой муравей не повторяет ни один путь другого). Если муравей не может пойти по своему уникальному пути, то он остается на ферме. Посчитайте, сколько муравьев сбежит с фермы и поселится в комнате Пети.

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

Вводятся два числа N и M - размеры таблицы (\(1<=N<=10\), \(1<=M<=10\)).

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

Выведите искомое количество способов.

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

Примеры

№	Входные данные	Выходные данные
1	1 10	1

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

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

Гомер Симпсон#33650

Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: 1 <=M, N, T, <= 1000000 , все числа целые.

Входные данные
В первой строке находятся три числа - M, N и T, разделённые пробелами.

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

Ввод	Вывод
1 2 1000	1000
2 1 1000	1000
3 6 1000	333 1

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

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

Наибольшая возрастающая подпоследовательность за O(n*log(n))#33231

Числовая последовательность задана рекуррентной формулой: a_i+1=(k * a_i+ b) mod m. Найдите длину её наибольшей возрастающей подпоследовательности.
mod - операция вычисления остатка от деления

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

Программа получает на вход пять целых чисел: длину последовательности n (1≤n≤10⁵), начальный элемент последовательности a₁, параметры k, b, m для вычисления последующих членов последовательности (1≤m≤10⁴, 0≤k<m, 0≤b<m, 0≤a1<m).

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

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

Примеры

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

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

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

Ход конем - 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лёгкаяВойти и решать

Копилка#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лёгкаяВойти и решать

Игра с пешкой#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средняяВойти и решать

Circular Barn#29547

У Фермера Джона круглый амбар. Амбар состоит из кольца из n комнат, пронумерованных 1…n по периметру (3≤n≤1,000). Каждая комната имеет двери в две соседние комнаты и одну дверь во внешний мир.

ФД хочет разместить ровно ri коров в комнате i (1≤r_i≤1,000,000). Он планирует открыть k внешних дверей (1≤k≤7), через которые коровы будут входить в амбар. Каждая корова затем идёт по часовой стрелке, пока не добредёт до нужной комнаты. ФД хочет открыть двери так, чтобы все коровы вместе прошли как можно меньшее расстояние. Коровы предварительно могут собраться как им выгоднее перед этими незакрытыми дверями (эти перемещения не входят в общее расстояние, учитываемое в задаче). Определите минимальное суммарное расстояние, которое придётся пройти коровам, если ФД наилучшим образом выберет какие k открыть.

ФОРМАТ ВВОДА:

Первая строка ввода содержит n и k. Последующие n строк содержат r₁…r_n.

ФОРМАТ ВВОДА:

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

Ввод	Вывод
6 2 2 5 4 2 6 2	14

ФД может открыть двери 2 и 5. 11 коров войдут в двери 2 и пройдут суммарное расстояние 8 чтобы попасть в комнаты 2,3,4. 10 коров войдут в дверь 5 и пройдут общее расстояние 6, чтобы попасть в комнаты 5,6,1.

Динамическое программирование Динамическое программирование: два параметра Задача на реализацию Рекурсия

✓ 1✗ 1—Войти и решать

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

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

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

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

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

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

Примеры

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

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

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

Расстояние по Левенштейну#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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

Cow Hopscotch#27296

Фермер Джон придумал игру для своих коров

Она играется на решётке R*C (2 <= R <= 750, 2 <= C <= 750), где каждый квадрат помечен целым числом от 1 до K (1 <= K <= R*C). Коровы выполняют последовательность прыжков, начиная в левом верхнем квадрате и заканчивая в правом нижнем квадрате и прыжок является корректным если и только если:

1) Вы прыгаете на квадрат c другим числом

2) Квадрат, куда Вы прыгаете, как минимум на одну строку ниже квадрата, в котором Вы сейчас стоите

3) Квадрат, в который Вы прыгаете как минимум на одну колонку правее квадрата, в котором Вы сейчас стоите

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

INPUT FORMAT:

Первая строка ввода содержит целые числа R, C, K. Каждая из следующих R строк содержит C целых чисел, каждое в интервале 1..K.

OUTPUT FORMAT:

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

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

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

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

Palindromic Paths#27294

Ферма Джона представлена решёткой N×N полей (1≤N≤500). Каждое поле представлено символом латинского алфавита. Например:

ABCD

BXZX

CDXB

WCBA

Каждый день корова Беси прогуливается из верхнего левого угла в правый нижний, каждый раз двигаясь на один шаг вправо или вниз. Беси записывает в строку буквы, по которым прошлась. Она огорчится, если у неё получится палиндром (слово, которое читается одинаково слева направо и справа налево), поскольку тогда она запутается, в каком направлении двигалась.

Пожалуйста, помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 1,000,000,007.

ФОРМАТ ВВОДА:

Первая строка ввода содержит N, и последующие N строк содержат N строк решётки, описывающей поля. Каждая строка содержит N символов в интервале A..Z.

ФОРМАТ ВЫВОДА:

Выведите количество различных путей Беси, формирующих палиндромы по модулю 1,000,000,007.

Ввод	Вывод
4 ABCD BXZX CDXB WCBA	12

Примечание:

Беси может сделать следующие палиндромы:

1 x "ABCDCBA"

1 x "ABCWCBA"

6 x "ABXZXBA"

4 x "ABXDXBA"

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

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

Little Difference#27120

Little Lidia likes playing with numbers. Today she has a positive integer n, and she wants to decompose it to the product of positive integers.

Because Lidia is little, she likes to play with numbers with little difference. So, all numbers in decomposition should differ by at most one. And of course, the product of all numbers in the decomposition must be equal to n. She considers two decompositions the same if and only if they have the same number of integers and there is a permutation that transforms the first one to the second one.
Write a program that finds all decompositions, which little Lidia can play with today.

Input
The only line of the input contains a single integer n (1 ≤ n ≤ 10¹⁸).

Output
In first line output the number of decompositions of n, or −1 if this number is infinite. If number of decompositions is finite, print all of them one per line. In each line first print number ki of elements in decomposition. Then print ki integers in this decomposition in any order. Don’t forget that decompositions which are different only in order of elements are considered the same.

Input	Output
12	3 1 12 3 2 3 2 2 4 3
1	-1

In the second example 1 can be represented as product of any number of ones.

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

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