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


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 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

ID 23377. НВП на отрезке (А, А')
Темы: Динамическое программирование: последовательности   

Нам дана числовая последовательность a1, ..., an . Напишите программу, отвечающую на запросы вида "найти длину наибольшей строго возрастающей подпоследовательности, все элементы которой находятся на отрезке с li-ого по ri-ый элемент".
Подпоследовательностью последовательности a1 , ..., an называется последовательность, которую можно получить путем удаления нескольких элементов ai (относительный порядок оставшихся элементов менять запрещается). Так, например, последовательность (2, 4) является подпоследовательностью последовательности (1, 2, 3, 4, 5) (можно удалить элементы 1, 3  и 5 ),  а последовательность (5, 1) - нет.
 
Входные данные
В первой строке записано целое число n  (1 <= n <= 3000 ) - число элементов в последовательности. Во второй строке записано n  чисел, разделенных пробелами - элементы последовательности. Все элементы не превосходят по модулю 109. В третьей строке записано одно целое число q  (1 <= q <= 105) - количество запросов. В следующих q  строках описаны запросы. Описание i -ого запроса - два числа li и rj (1 <= li <= ri <= 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

ID 27120. Little Difference
Темы: Динамическое программирование: последовательности    Конструктив   

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 ≤ 1018).

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.

ID 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

 

ID 33231. Наибольшая возрастающая подпоследовательность за O(n*log(n))
Темы: Динамическое программирование    Динамическое программирование: последовательности    Динамическое программирование: последовательности   

Числовая последовательность задана рекуррентной формулой: ai+1=(k * a+ b) mod m. Найдите длину её наибольшей возрастающей подпоследовательности. 
mod - операция вычисления остатка от деления 
 
Входные данные
Программа получает на вход пять целых чисел: длину последовательности n (1≤n≤105), начальный элемент последовательности a1, параметры k, b, m для вычисления последующих членов последовательности (1≤m≤104, 0≤k<m, 0≤b<m, 0≤a1<m).
 
Выходные данные
Требуется вывести длину наибольшей возрастающей подпоследовательности данной последовательности.

 
Примеры
Входные данные Выходные данные
1
5 41 2 1 100
3

ID 33231. Наибольшая возрастающая подпоследовательность за O(n*log(n))
Темы: Динамическое программирование    Динамическое программирование: последовательности    Динамическое программирование: последовательности   

Числовая последовательность задана рекуррентной формулой: ai+1=(k * a+ b) mod m. Найдите длину её наибольшей возрастающей подпоследовательности. 
mod - операция вычисления остатка от деления 
 
Входные данные
Программа получает на вход пять целых чисел: длину последовательности n (1≤n≤105), начальный элемент последовательности a1, параметры k, b, m для вычисления последующих членов последовательности (1≤m≤104, 0≤k<m, 0≤b<m, 0≤a1<m).
 
Выходные данные
Требуется вывести длину наибольшей возрастающей подпоследовательности данной последовательности.

 
Примеры
Входные данные Выходные данные
1
5 41 2 1 100
3

ID 47742. Магическая подпоследовательность Айвена
Темы: Динамическое программирование    Динамическое программирование: последовательности   

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

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

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

Примеры
Входные данные Выходные данные
1
bbbab
4

ID 47746. Фишки-палочки
Темы: Динамическое программирование    Динамическое программирование: последовательности   

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

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

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

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


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

Ограничения

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


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

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