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


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


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