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

Snakes#90077

У Беси есть сеть ловить змеек, распределённых в \(N\) групп на линии \((1 \leq N \leq 400)\). Беси должна поймать каждую змейку в каждой группе. Каждый раз, когда Беси ловит группу она может переложить змеек в клетку и начать пустой сеткой ловить следующую группу.

Сеть размером \(s\) означает, что Беси может поймать любую группу, которая содержит \(g\) змеек, где \(g \leq s\). Однако каждый раз, когда Беси ловит группу змеек размером \(g\) сетью размером \(s\), она тратит впустую \(s - g\) пространства. Беси может начинать с сети любого размера и Беси может изменять размер своей сети \(K\) раз \((1 \leq K < N)\).

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

ФОРМАТ ВВОДА (файл snakes.in):

Первая строка содержит \(N\) и \(K\). Вторая строка содержит \(N\) целых чисел \(a_1,\dots,a_N\), где \(a_i\) (\(0 \leq a_i \leq 10^6\)) количество змеек в \(i\)-ой группе.

ФОРМАТ ВЫВОДА (файл snakes.out):

Выведите одно целое число - минимальное количество потерянного пространства после того как Беси выловит всех змеек.

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

—Войти и решать

Анаграммер#55695

Анаграммер — специальное устройство для получения из слова его анаграмм (то есть слов, записанных теми же буквами, но в другом порядке). Это устройство умеет выполнять 2 операции:

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

Стек — это хранилище данных, которое работает по принципу "первый пришел — последний ушел". Стек можно представить себе в виде пирамидки. Когда мы добавляем букву в стек, это соответствует тому, что на стержень пирамидки сверху мы надеваем кольцо, на котором написана соответствующая буква. Когда берем букву из стека, то это соответствует тому, что мы снимаем со стержня верхнее кольцо, и смотрим, какая буква на нем написана.

Например, слово TROT в слово TORT может быть преобразовано анаграммером двумя различными последовательностями операций: 11112222 или 12112212.

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

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

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

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

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

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

Головоломка#55002

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

Для задания конфигурации головоломки удобно рассмотреть ее развертку - "разрезать" поверхность цилиндра вдоль вертикальной линии, проходящей по границам квадратиков, и обозначить черные клетки символом "1", а белые - символом "0". Пусть, например, одна из возможных разверток головоломки, приведенной на рисунке, следующая (на рисунке видно только первые три столбца этой развертки):
000110 001110 101000 001000 011111 011110
Задача решающего головоломку состоит в том, чтобы, поворачивая слои, добиться того, чтобы все вертикальные столбцы были различны. Например, головоломка приведенная выше, не решена, поскольку два из ее столбцов (четвертый и пятый на приведенной развертке) одинаковы. Если же повернуть нижний слой влево на один квадратик, развертка головоломки примет следующий вид:
000110 001110 101000 001000 011111 111100
Теперь все столбцы различны и, следовательно, головоломка решена.

Для того, чтобы решать головоломку было интереснее, на ее раскраску наложено дополнительное условие: нельзя повернуть один из слоев головоломки меньше, чем на полный оборот таким образом, что внешний вид головоломки останется тем же. Так, например, для n = 6 слой с раскраской "010101" не разрешается, поскольку при его повороте на 2 квадратика внешний вид головоломки не меняется.

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

Входные данные
В первой строке вводится число n  - количество слоев в головоломке и количество квадратиков в одном слое (1 <= n  <= 200). Следующие n
строк содержат по n  символов, каждый из которых равен 0 или 1 - развертку головоломки.

Выходные данные
Если решить головоломку можно, в первой строке выведите слово "Yes". В этом случае следующие n  строк должны содержать произвольную развертку решенной головоломки.

Если решить головоломку нельзя, выведите в первой и единственной строке выходных данных слово "No".

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

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

Лестница#53814

Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 1 (один) метр, из М ступенек различной длины и высоты. Лестница построена из каменных блоков 1x1x1 метр. Археологи хотят для удобства туристов, чтобы лестница состояла из меньшего количества ступенек N. Для этого они могут также устанавливать каменные блоки 1x1x1. Какое минимальное количество блоков необходимо, чтобы сделать лестницу в N ступенек, если известны начальная длина и высота каждой ступеньки. Высоты и длины ступенек новой лестницы могут различаться.

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

В первой строке через пробел заданы два целых числа M и N (1 <= N < M <= 100). Далее идут M строк, содержащих пару целых чисел L и H - длина и высота i-ой ступеньки соответственно (1 <= L, H <= 101). Ступеньки нумеруются снизу вверх.

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

В выходной файл выведите единственное число - ответ на задачу.

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

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

Фишки-палочки#47746

Алиса и Громозека играют в фишки-палочки. У каждого из них есть набор фишек, на каждой фишке записано одно целое число. Каждый из них выкладывает свои фишки вдоль двух параллельных горизонтальных линий. Следующим шагом Алиса соединяет палочкой две фишки, расположенные на разных горизонтальных линиях, то есть соединяет одну свою фишку с одной из фишек Громозеки по следующим правилам:

числа, на фишке Алисы и на фишке Громозеки равны;
соединяющая палочка не должна пересекать другие палочки;
две палочки не могут указывать на одну и ту же фишку.

Далее, Громозека считает сколько палочек выложила Алиса. После этого, Алиса убирает свои палочки и фишки соединяет Громозека по тем же правилам. Выигрывает тот, кто выложит по данным правилам больше всего палочек.

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

Входные данные
Первая строка входных данных содержит число n - количество фишек Алисы. Вторая строка содержит n чисел nums1_i - числа на фишках Алисы, в том порядке, в котором она их выложила. Третья строка содержит число m - количество фишек Громозеки. Четвертая строка содержит m чисел nums2_j - числа на фишках Громозека, в том порядке, в котором он их выложил.

Ограничения

1 <= n, m <= 500
1 <= nums1[i], nums2[j] <= 2000

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

Примечание
Рисунок к первому тестовому примеру

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

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

Магическая подпоследовательность Айвена#47742

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

Входные данные
Программа получает на вход последовательность символов s (1<= |s| <= 1000), состоящую из строчных английских букв.

Выходные данные
Выведите одно число - длину самой длинной магической подпоследовательности.

Примеры

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

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

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

Кинотеатр#38189

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

Входные данные
Вводятся два числа — X и Y (оба числа натуральные, не превосходящие 100).

Выходные данные
Выведите какую-нибудь строку, в которой будет ровно X символов B (обозначающих мальчиков) и Y символов G (обозначающих девочек), удовлетворяющую условию задачи. Пробелы между символами выводить не нужно. Если рассадить мальчиков и девочек согласно условию задачи невозможно, выведите строку NO SOLUTION.

Примеры

№	Входные данные	Выходные данные
1	5 5	BGBGBGBGBG
2	5 3	BGBGBBGB
3	100 1	NO SOLUTION

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

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

Наибольшая возрастающая подпоследовательность за 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средняяВойти и решать

Наибольшая общая подпоследовательность с восстановлением ответа#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

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

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

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

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

Примеры

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

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

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

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

Упорядочите шарики#27053

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

Для того, чтобы упорядочить шарики перед началом следующей партии, используется следующее устройство. Это устройство состоит из головки, которая, перемещаясь над шариками, может «засасывать» и «выплевывать» шарики. Чтобы получить большее представление об этом устройстве, представьте себе пылесос, который может засасывать шарики, перемешаться в нужное место, и там, включаясь на продув в обратном направлении, шарики «выплевывать».

При засасывании шарика все шарики, которые находились правее засасываемого, сдвигаются влево. «Выплюнуть» шарик можно между любыми двумя шариками (а также перед первым шариком или после последнего), тогда выплевываемый шарик вставляется между этими шариками, и все шарики, которые находятся правее вставляемого, сдвигаются вправо.

В устройство может быть одновременно засосано больше одного шарика, при этом при выплевывании шарика первым выплевывается последний засосанный шарик, затем - предпоследний и т.д. (т.е. устройство работает по принципу стека). Шарики выплевываются по одному, т.е. можно выплюнуть только один шарик, остальные оставив внутри устройства (при этом дальше можно как продолжать «выплевывать» шарики в том же или в другом месте, так и засасывать новые шарики).

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

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

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

Во входном файле задано сначала число N — количество шариков (1<= N <= 1000). Далее идет N чисел, задающих номера шариков в порядке слева направо в их текущем расположении (каждое число — от 1 до N, и каждое из чисел встречается в последовательности ровно один раз).

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

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

Комментарии к примерам тестов

1.Можно засосать, например, шарик номер 2 и выплюнуть его между 1-м и 3-м шариком.

2. Можно действовать, например, так. Сначала засосем шарик номер 1, затем – шарик номер 2. Затем переместимся в начало и перед 4-м шариком выплюнем шарик (это будет шарик номер 2). Дальше засосем шарик номер 3, и выплюнем его между шариками 2 и 4. Дальше переместимся в начало и там выплюнем шарик номер 1. Впрочем, это не единственный возможный вариант упорядочения шариков в этом примере.

Примеры

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

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

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

Возрастающая подпоследовательность#27052

Даны N целых чисел X₁, X₂, ..., X_N. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

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

В первой строке находится число N. В следующей строке - N чисел через пробел. 1 <= N <= 10 000, 1 <= X_i <= 60 000.

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

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

Примеры

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

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

✓ 221✗ 1 024700средняяВойти и решать

Подпоследовательности#23409

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

подпоследовательности.

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

В первой строке входного файла записано число N - длина последовательности (1 <= N <= 1000). Во второй строке записана сама последовательность (через пробел). Числа последовательности - целые числа, не превосходящие 10000 по модулю.

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

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

Примеры

№	Входные данные	Выходные данные
1	6 3 29 5 5 28 6	3

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

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

НВП на отрезке#23377

Нам дана числовая последовательность a₁, ..., a_n . Напишите программу, отвечающую на запросы вида "найти длину наибольшей строго возрастающей подпоследовательности, все элементы которой находятся на отрезке с l_i-ого по r_i-ый элемент".

Подпоследовательностью последовательности a₁ , ..., a_n называется последовательность, которую можно получить путем удаления нескольких элементов a_i (относительный порядок оставшихся элементов менять запрещается). Так, например, последовательность (2, 4) является подпоследовательностью последовательности (1, 2, 3, 4, 5) (можно удалить элементы 1, 3 и 5 ), а последовательность (5, 1) - нет.

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

В первой строке записано целое число n (1 <= n <= 3000 ) - число элементов в последовательности. Во второй строке записано n чисел, разделенных пробелами - элементы последовательности. Все элементы не превосходят по модулю 10⁹. В третьей строке записано одно целое число q (1 <= q <= 10⁵) - количество запросов. В следующих q строках описаны запросы. Описание i -ого запроса - два числа l_i и r_j (1 <= l_i <= r_i <= n) , записанные через пробел.

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

Выведите q чисел - ответы на запросы. Числа следует выводить по одному на строке в том же порядке, в котором запросы описаны во вводе.

Примеры

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

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

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