Codeforces Round #627 (Div. 3)
A. Yet Another Tetris Problem
You are given some Tetris field consisting of n columns. The initial height of the i-th column of the field is ai blocks. On top of these columns you can place only figures of size (i.e. the height of this figure is blocks and the width of this figure is block). Note that you cannot rotate these figures.
Your task is to say if you can clear the whole field by placing such figures.
More formally, the problem can be described like this:
The following process occurs while at least one is greater than :
You place one figure (choose some from to and replace with );
then, while all ai are greater than zero, replace each with .
And your task is to determine if it is possible to clear the whole field (i.e. finish the described process), choosing the places for new figures properly.
You have to answer t independent test cases.
Input
The first line of the input contains one integer — the number of test cases.
The next lines describe test cases. The first line of the test case contains one integer — the number of columns in the Tetris field. The second line of the test case contains n integers , where is the initial height of the -th column of the Tetris field.
Output
For each test case, print the answer — “YES” (without quotes) if you can clear the whole Tetris field and “NO” otherwise.
Example
input
4
3
1 1 3
4
1 1 2 1
2
11 11
1
100
output
YES
NO
YES
YES
Note
The first test case of the example field is shown below:
Gray lines are bounds of the Tetris field. Note that the field has no upper bound.
One of the correct answers is to first place the figure in the first column. Then after the second step of the process, the field becomes . Then place the figure in the second column and after the second step of the process, the field becomes .
And the second test case of the example field is shown below:
It can be shown that you cannot do anything to end the process.
In the third test case of the example, you first place the figure in the second column after the second step of the process, the field becomes . Then place the figure in the first column and after the second step of the process, the field becomes .
In the fourth test case of the example, place the figure in the first column, then the field becomes after the first step of the process, and then the field becomes after the second step of the process.
Translation
玩俄罗斯方块,但是只能一次竖着放几个的方块。问能不能一次性把所有方块消除。
Idea
消除方块就要填满所有的坑,如果相邻两个方块直接相差的个数是的倍数,那就能用几个的方块竖着填满。
Code
1 |
|
Postscript
一开始了一发,把条件语句写成了if((a[i+1]-a[i])%2==1)
,如果就尴尬了。
B. Yet Another Palindrome Problem
You are given an array a consisting of n integers.
Your task is to determine if a has some subsequence of length at least that is a palindrome.
Recall that an array b is called a subsequence of the array a if b can be obtained by removing some (possibly, zero) elements from a (not necessarily consecutive) without changing the order of remaining elements. For example, , and are subsequences of , but and are not.
Also, recall that a palindrome is an array that reads the same backward as forward. In other words, the array of length is the palindrome if for all from to n. For example, arrays and are palindromes, but arrays and are not.
You have to answer t independent test cases.
Input
The first line of the input contains one integer — the number of test cases.
Next lines describe test cases. The first line of the test case contains one integer — the length of . The second line of the test case contains integers , where is the -th element of .
It is guaranteed that the sum of n over all test cases does not exceed $ (∑n≤5000)$.
Output
For each test case, print the answer — “YES” (without quotes) if a has some subsequence of length at least 3 that is a palindrome and “NO” otherwise.
Example
input
5
3
1 2 1
5
1 2 2 3 2
3
1 1 2
4
1 2 2 1
10
1 1 2 2 3 3 4 4 5 5
output
YES
YES
NO
YES
NO
Note
In the first test case of the example, the array a has a subsequence which is a palindrome.
In the second test case of the example, the array a has two subsequences of length which are palindromes: and .
In the third test case of the example, the array a has no subsequences of length at least which are palindromes.
In the fourth test case of the example, the array a has one subsequence of length which is a palindrome: (and has two subsequences of length which are palindromes: both are ).
In the fifth test case of the example, the array a has no subsequences of length at least which are palindromes.
Translation
问是否能在数列中找到一个长度大于等于的回文子序列。
Idea
只需要满足最低要求,找数列中长度为的回文子序列即可。
这样的子序列存在满足两个条件
- 有两个重复数字
- 两个重复数字之间的索引差值大于
Code
1 |
|
C. Frog Jumps
There is a frog staying to the left of the string consisting of characters (to be more precise, the frog initially stays at the cell ). Each character of is either ‘L’ or ‘R’. It means that if the frog is staying at the -th cell and the -th character is ‘L’, the frog can jump only to the left. If the frog is staying at the -th cell and the -th character is ‘R’, the frog can jump only to the right. The frog can jump only to the right from the cell .
Note that the frog can jump into the same cell twice and can perform as many jumps as it needs.
The frog wants to reach the -th cell. The frog chooses some positive integer value before the first jump (and cannot change it later) and jumps by no more than cells at once. I.e. if the -th character is ‘L’ then the frog can jump to any cell in a range , and if the -th character is ‘R’ then the frog can jump to any cell in a range .
The frog doesn’t want to jump far, so your task is to find the minimum possible value of such that the frog can reach the cell from the cell if it can jump by no more than cells at once. It is guaranteed that it is always possible to reach from .
You have to answer t independent test cases.
Input
The first line of the input contains one integer — the number of test cases.
The next t lines describe test cases. The -th test case is described as a string s consisting of at least and at most characters ‘L’ and ‘R’.
It is guaranteed that the sum of lengths of strings over all test cases does not exceed .
Output
For each test case, print the answer — the minimum possible value of d such that the frog can reach the cell from the cell if it jumps by no more than d at once.
Example
input
6
LRLRRLL
L
LLR
RRRR
LLLLLL
R
output
3
2
3
1
7
1
Note
The picture describing the first test case of the example and one of the possible answers:
In the second test case of the example, the frog can only jump directly from to .
In the third test case of the example, the frog can choose , jump to the cell from the cell 0 and then to the cell from the cell .
In the fourth test case of the example, the frog can choose and jump times to the right.
In the fifth test case of the example, the frog can only jump directly from to .
In the sixth test case of the example, the frog can choose and jump times to the right.
Translation
青蛙在一排只有’L’和’R’的字符串(字符串从1~n)上跳,碰到’L’向左跳,碰到’R’向右跳,青蛙每次最多能跳个长度,问使得青蛙能从跳到的最小的。
Idea
根据,我们根本不需要向左跳。 这只会远离我们的目标,因为在向左跳后我们的自由度降低了。 为了最小化,我们只需要在最接近的’R’单元之间跳转即可。任务就是求出相邻’R’的最大间隔。
因为要从跳转到,所以开头和末尾添加一个为’R’的格子。
Code
1 |
|
D. Pair of Topics
The next lecture in a high school requires two topics to be discussed. The -th topic is interesting by ai units for the teacher and by bi units for the students.
The pair of topics and is called good if (i.e. it is more interesting for the teacher).
Your task is to find the number of good pairs of topics.
Input
The first line of the input contains one integer — the number of topics.
The second line of the input contains integers , where is the interestingness of the -th topic for the teacher.
The third line of the input contains integers , where is the interestingness of the -th topic for the students.
Output
Print one integer — the number of good pairs of topic.
Examples
input
5
4 8 2 6 2
4 5 4 1 3
output
7
input
4
1 3 2 4
1 3 2 4
output
0
Translation
给两个数列${ a_n } , { b_n } a_i+a_j>b_i+b_j(i<j)(i,j)$对的个数。
Idea
,令,则问题转化为求的对的个数,实际上就是在数列中不考虑顺序地不重复得选取个满足条件的数对,问的最大值。
将从大到小排序,可以用对于每一个,若,在前面一定找不到使得的;若,需要二分找到第一个大于的数字的位置,那么答案增加。
Code
1 |
|
E. Sleeping Schedule
Vova had a pretty weird sleeping schedule. There are hours in a day. Vova will sleep exactly times. The -th time he will sleep exactly after hours from the time he woke up. You can assume that Vova woke up exactly at the beginning of this story (the initial time is ). Each time Vova sleeps exactly one day (in other words, hours).
Vova thinks that the -th sleeping time is good if he starts to sleep between hours and inclusive.
Vova can control himself and before the -th time can choose between two options: go to sleep after hours or after hours.
Your task is to say the maximum number of good sleeping times Vova can obtain if he acts optimally.
Input
The first line of the input contains four integers and $ (1≤n≤2000,3≤h≤2000,0≤l≤r<h)$ — the number of times Vova goes to sleep, the number of hours in a day and the segment of the good sleeping time.
The second line of the input contains n integers , where is the number of hours after which Vova goes to sleep the -th time.
Output
Print one integer — the maximum number of good sleeping times Vova can obtain if he acts optimally.
Example
input
7 24 21 23
16 17 14 20 20 11 22
output
3
Note
The maximum number of good times in the example is .
The story starts from . Then Vova goes to sleep after hours, now the time is . This time is not good. Then Vova goes to sleep after hours, now the time is . This time is also not good. Then Vova goes to sleep after hours, now the time is . This time is good. Then Vova goes to sleep after hours, now the time is . This time is not good. Then Vova goes to sleep after hours, now the time is . This time is not good. Then Vova goes to sleep after hours, now the time is . This time is good. Then Vova goes to sleep after hours, now the time is . This time is also good.
Translation
一天有小时,主人公要睡次觉,第次睡觉可以睡小时或者个小时,醒了马上就要睡下一觉,直到睡完次,如果睡觉起来的时刻在到之间,那么这一觉就是,加一分,问睡完这次,最多得多少分。
Idea
此题是一个最优化问题,且满足最优子结构,考虑使用。
正如官方题解所说:“This is a very standard dynamic programming problem.”然而我wa了5次,比赛结束了还没做出来。
表示睡完第次时,有次睡了个小时,次睡了个小时的最大得分。
转移方程很好想,由和得到。转移后需要判断的状态是否good。
Code
1 |
|
Postscript
完成后,找答案的循环必须从开始。