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

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

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

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

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

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

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

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

Примеры

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

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

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

Palindromic Paths#28324

Ферма Джона представлена решёткой из N×N полей(2≤N≤18), каждое из которых помечено буквой алфавита. Например,

ABCD

BXZX

CDXB

WCBA

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

Пожалуйста, помогите Беси определить количество различных палиндромов, которые она сможет сформировать во время своего путешествия. Различные способы формировать один и тот же палиндром следует учитывать только один раз. Например, в примере выше имеется несколько способов сформировать палиндром ABXZXBA, однако существует всего 4 различных палиндрома, которые Беси может сформировать ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.

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

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

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

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

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

meet in the middle Перебор

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

Cow Curling#27300

В коровий кёрлинг вовлечены две команды, каждая из которых двигает N тяжёлых камней (3 <= N <= 50,000) по льду. В конце игры имеется 2N камней на льду, каждый из которых расположен в различной точке

плоскости.

Подсчёт очков в коровьем кёрлинге ведётся следующим образом:

Камень считается «захваченным», если он содержится внутри треугольника, по углам которого находятся камни противника (камень, который находится на границе такого треугольника, также считается захваченным). Счёт команды есть количество камней команды противника, которые «захвачены».

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

INPUT FORMAT:

* Строка 1: Целое число N.

* Строки 2..1+N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды A (каждая координата лежит в диапазоне -40,000 .. +40,000).

* Строки 2+N..1+2N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды B (каждая координата лежит в диапазоне -40,000 .. +40,000).

OUTPUT FORMAT:

* Строка 1: Два разделённых пробелом целых числа, представляющих счета команд A и B

SAMPLE:

Ввод	Вывод
4 0 0 0 2 2 0 2 2 1 1 1 10 -10 3 10 3	1 2

INPUT DETAILS:

У каждой команды по 4 камня.

Команда A имеет камни (0,0), (0,2), (2,0), (2,2).

Команда B имеет камни (1,1), (1,10), (-10,3), (10,3).

OUTPUT DETAILS:

Команда A захватила камень противника в точке (1,1).

Команда B захватила камни противника в точках (0,2) и (2,2).

Вычислительная геометрия Динамическое программирование Структуры данных

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

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

Черепаха#27086

Черепаха хочет переползти из левого верхнего угла поля размером N на M клеток ( 1 ≤ N , M ≤ 16 ) в правый нижний. За один шаг она может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Определите, сколькими различными способами Черепаха может добраться до цели.

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

Входная строка содержит два натуральных числа: размеры поля N и M , разделённые пробелом ( 1 ≤ N , M ≤ 16 ).

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

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

Примеры

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

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

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

Зоомагазин#27083

В зоомагазине нужно расставить в один ряд клетки с животными. В ряд помещается N клеток, при этом есть одно ограничение: нельзя ставить рядом две клетки с собаками (иначе они передерутся). Предполагается, что в магазине есть неограниченное количество клеток с разными животными. Определите, сколькими безопасными способами можно расставить N клеток в ряд.

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

Входная строка содержит одно натуральное число – количество клеток в ряду N .

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

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

Ввод	Вывод
5	13

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

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

Кузнечик-KMax#27081

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад.

Поскольку количество способов, которое нужно найти, может быть очень велико, вычислите его по модулю \(10^6 + 7\) , то есть найдите остаток от деления этого числа на \(10^6 + 7\) .

Входные данные: входная строка содержит натуральные числа N и K, разделённые пробелом. Гарантируется, что \(1 <= N ,\ K <= 10000\).

Выходные данные: программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N , вычисленное по модулю \(10^6+7\).

Примеры

№	Входные данные	Выходные данные
1	10 5	236
2	100 50	934384

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

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

Кузнечик-K#27080

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад.

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

Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 ≤ N , K ≤ 32 .

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

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

Ввод	Вывод
5 4	8

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

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

Кузнечик#27079

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть на следующий столбик или сразу на второй столбик, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад.

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

Входная строка содержит натуральное число N ( 1 ≤ N ≤ 45 ).

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

Ввод	Вывод
3	2
10	55

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

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

Кузнечик собирает монеты#27069

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

Входные данные
- в первой строке вводятся два натуральных числа: N и K (\(2 <= N ,\ K <= 10000\)), разделённые пробелом;
- во второй строке записаны через пробел N-2 целых числа – количество монет, которое Кузнечик получает на каждом столбике, от 2-го до N-1-го. Если это число отрицательное, Кузнечик теряет монеты.
Гарантируется, что все числа по модулю не превосходят 10000.

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

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

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

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

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

Capybara. Канатная дорога#27068

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

Известно, что лес состоит из n деревьев, стоящих в ряд и пронумерованных слева направо числами от 1 до n. Высота i-го дерева, по воспоминаниям Васи, равна h_i. Канатная дорога длины k должна опираться на k (1 <= k <= n) деревьев i₁, i₂, . . . , i_k (i₁ < i₂ < . . . < i_k), таких что их высота возрастает, то есть, h_i1 < h_i2 < . . . < h_ik.

Петя тоже был в лесу, и у него есть q предположений о том, где именно ошибается Вася. Его i-е предположение задаётся числами a_i и b_i , означающими, что, по мнению Пети, высота дерева

с номером a_i на самом деле равна b_i . Обратите внимание, Петины предположения независимы между собой.

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

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

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

Первая строка входных данных содержит два числа n и m (1 <= n, m <= 400 000) — количество деревьев в лесу и количество предположений Пети соответственно.

В следующей строке содержатся n целых чисел h_i (1 <= h_i <= 10⁹ ) — высоты деревьев по предположению Васи.

Каждая из следующих m строк содержит по два целых числа a_i и b_i (1 <= a_i <= n, 1 <= b_i <= 10⁹ ).

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

Для каждого предположения Пети выведите в отдельной строке одно число — максимальную длину канатной дороги.

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

Замечание

Рассмотрим первый пример. Первое Петино предположение совпадает с предположением Васи.

Согласно его второму предположению, высоты деревьев были (4, 2, 3, 4), третьему (1, 2, 3, 3), а по четвёртому предположению — (1, 2, 3, 5).

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

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

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

Обход по графу. Построение дерева решений#27035

Разработан шифр, при использовании которого каждой цифре ставится в

соответствие определенная буквенная последовательность как приведено в таблице.

1	2	3	4	5	6	7
AB	CB	CBA	ABC	BC	BBC	CCB

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

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

Ввод	Вывод
ABCCBABBCCBABC	6

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

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

Пароль#26999

Антон вводит пароль. Артур подглядывает за Антоном и записывает последовательность клавиш, которые тот нажимает. Иногда Артур не разбирает клавишу и пишет вместо неё символ «*». Артур знает, что пароль Антона является сочетанием (без пробелов) его часто произносимых слов.

Каждое слово может присутствовать в пароле любое количество раз, в том числе 0. Артур решил восстановить пароль Антона. Какое минимальное количество вариантов ему потребуется перебрать?

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

В первой строке находятся два числа N и K (1 <= N <=1000,1 <=K <= 10). Во второй строке находится строка из N символов - последовательность, которую записал Артур. Последовательность может содержать строчные буквы латинского алфавита и знак «*».

Далее идут K строк, которые обозначают часто произносимые слова Антона. Каждое слово состоит не более чем из 10 строчных латинских букв. Других символов в словах нет.

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

Если количество вариантов не более 10⁹, выведите это количество. Иначе выведите единственную строку «MNOGO».

Ввод	Вывод
12 3 r*mm** mama mila ramu	4
10 8 ********** a b c d e f g h	MNOGO

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

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

Разбиения на сумму нечетных#26985

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

Например, число 6 можно разложить на слагаемые следующими способами: 1+1+1+1+1+1, 1+1+1+3, 3+3, 1+5.

Формат ввода

На вход подается число n (1 n 1000).

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

Выведите одно число — ответ на задачу.

Пример

Ввод	Вывод
6	4

Примечания

Разбиение, состоящее из одного слагаемого, также считается разбиением.

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

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

Пути в музее#26978

Болик добрался до музея, здание которого представляет собой квадрат N × N, разбитый на N² равных квадратных залов. Вход в музей расположен в левом нижнем зале, а Лёлик ждет Болика в правом верхнем. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).

Теперь Болик хочет определить сколько возможных путей до Лёлика у него есть. Конечно, его интересуют только пути кратчайшей длины.

Формат ввода

На вход подается одно натуральное число N (2 ≤ N ≤ 22).

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

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

Пример

Ввод	Вывод
3	6

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

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

Это Бомба#24906

Мише приснился страшный сон как будто ему очень быстро необходимо разминировать бомбу! На большом дисплее бомбы он видит одно число, рядом есть клавиатура с цифрами (явно для экстренной отмены взрыва), а где-то внизу уже идёт обратный отсчёт. По удачному стечению обстоятельств у него с собой есть инструкция для разминирования, в которой ему нужно срочно разобраться. В такой тяжялой ситуации мозги у Миши совсем отказали и ему явно нужна помощь.

Инструкция:

Посчитайте числовой код для числа на дисплее соответственно приведённым правилам и введите его. Применяется первое подошедшее правило:

1. Если число <= 2, то числовой код равен 1.

2. Если число заканчивается на 7, то нужно отнять от него 5. Посчитайте числовой код для нового числа и прибавьте 1.

3. Если число делится на 4 без остатка, его числовой код равен сумме кодов для числа,делённого на 4 и числа, делённого на 2.

4. Во всех остальных случаях к числу нужно прибавить 1. Посчитайте числовой код для нового числа и прибавьте 2.

Какой числовой код нужно ввести Мише?

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

В единственной строке содержится одно число от 1 до 10⁸, которое отображается на дисплее.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

Ввод	Вывод
1	1
10	12

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

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

Максимальная прибыль#24755

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

Про каждую задачу известно время t_i, которое нужно затратить, чтобы сделать её, а также прибыль p_i, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

Суммарное время, затраченное на выполнение задач, включённых в план, не превышало T.
Суммарная прибыль от выполнения этих задач была максимальна.

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

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

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

В первой строке находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа t_i и p_i (1 <= t_i, p_i <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

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

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

Примеры

№	Входные данные	Выходные данные
1	10 3 8 100 3 10 3 10	100
2	10 4 5 10 5 20 2 5 2 6	31

битмаски Задача о рюкзаке

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

Вупсень и Пупсень 2#24637

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

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

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

В первой строке дана строка s, во второй строке строка t, состоящие из строчных латинских букв. 1 <= |s|, |t| <= 50.

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

Выведите одно целое число n - длину наибольшей общей подпоследовательности, являющейся палиндромом.

Примеры

Ввод	Вывод
mem kek	1
acab abca	3

(с) Буков Антон, 11и

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

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

Пустоты в кубе#23588

Жюри составило отчет об учебно-тренировочных сборах по информатике и собирается распечатать его на стандартном листе бумаги. Весь отчет набран одним моноширинным шрифтом, т.е. все символы (включая пробелы) имеют одинаковую ширину. Длина строки при печати этим шрифтом на листе бумаги равна S.

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

Для достижения требуемого расположения текста на бумаге разрешается заменять произвольную пробельную последовательность (т.е. непустую последовательность подряд идущих пробелов или символов перевода строки) любой другой пробельной последовательностью.

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

Первая строка входного файла содержит целое число S (1<=S<=80).

В последующих строках записан отчет, содержащий не более 500 слов.

Длина каждой строки отчета не превосходит 250 символов, а длина каждого слова не превос-ходит S.

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

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

кубов пустот по всем строкам. В последующие строки следует вывести

искомое расположение текста на листе бумаги.

Пример входного файла

Победители летних учебно-тренировочных сборов по информатике 1997 г.:

Владимир Мартьянов,

Анатолий Пономарев,

Николай Дуров,

Андрей Лопатин.

Пример выходного файла

325

Победители летних

учебно-тренировочных сборов по

информатике 1997 г.: Владимир

Мартьянов, Анатолий Пономарев,

Николай Дуров, Андрей Лопатин.

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

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