Dynamic Programming: Sequences


Plus
Pin


Problem description Progress
ID 38189. Cinema
Темы: Dynamic Programming: Sequences   

X boys and Y girls went to the cinema and bought tickets for consecutive seats in the same row. Write a program that will tell you how boys and girls should sit so that at least one girl sits next to each boy, and next to each girl — at least one boy.

Input
Enter two numbers — X and Y (both natural numbers not exceeding 100).

Imprint
Print some string containing exactly X characters B (denoting boys) and Y characters G (denoting girls) that satisfies the condition of the problem. Spaces between characters are not required. If it is impossible to seat the boys and girls according to the condition of the problem, print the string NO SOLUTION.

Examples

# Input Output
1 5 5 BGBGBGBGBG
2 5 3 BGBGBBGB
3 100 1 NO SOLUTION

ID 23377. NVP on the segment (A, A')
Темы: Dynamic Programming: Sequences   

We are given a number sequence a1, ..., an . Write a program that responds to queries like "find the length of the largest strictly increasing subsequence, all elements
that are on the segment from the lith to the rith element".
A subsequence of the sequence a1 , ..., an is a sequence that can be obtained by removing several ai elements (the relative order of the remaining
elements cannot be changed). So, for example, the sequence (2, 4) is a subsequence of the sequence (1, 2, 3, 4, 5) (you can delete the elements 1, 3   and 5 ),  and the sequence (5, 1) is not.< br />  
Input
The first line contains an integer n  (1 <= n <= 3000 ) is the number of elements in the sequence. The second line contains n  Numbers separated by spaces are the elements of the sequence. All elements do not exceed 109 in absolute value. The third line contains a single integer q  (1 < ;= q <= 105) - number of requests. The following q  lines describe the queries. Description of the i -th query - two numbers li and rj  (1 <= li <= ri <= n) , separated by spaces.
 
Output data
Output q numbers - answers to queries. Numbers should be output one per line in the same order as the queries are described in the input.
 
Examples
# Input Output
1 6
3 3 -5 7 4 9
6
14
1 2
23
15
3 5
25		 2
1
1
2
2
2