AtCoder Beginner Contest 159
A - The Number of Even Pairs
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : points
Problem Statement
We have balls, each of which has an integer written on it.
It is known that:
The numbers written on of the balls are even.
The numbers written on of the balls are odd.
Find the number of ways to choose two of the balls (disregarding order) so that the sum of the numbers written on them is even.
It can be shown that this count does not depend on the actual values written on the balls.
Constraints
All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1
2 1
Sample Output 1
1
For example, let us assume that the numbers written on the three balls are .
If we choose the two balls with and , the sum is odd;
If we choose the two balls with and , the sum is odd;
If we choose the two balls with and , the sum is even.
Thus, the answer is .
Sample Input 2
4 3
Sample Output 2
9
Sample Input 3
1 1
Sample Output 3
0
Sample Input 4
13 3
Sample Output 4
81
Sample Input 5
0 3
Sample Output 5
3
Translation
有个球,个球上面写着偶数,个球上面写着奇数,要从这个球中选取两个球,使得两个球上写的数字的和为偶数,问有多少种选法。
Idea
同奇偶性的两个数相加为偶数,所以答案为。
Code
1 |
|
B - String Palindrome
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : points
Problem Statement
A string of an odd length is said to be a strong palindrome if and only if all of the following conditions are satisfied:
is a palindrome.
Let be the length of . The string formed by the -st through -th characters of is a palindrome.
The string consisting of the -st through -th characters of is a palindrome.
Determine whether is a strong palindrome.
Constraints
consists of lowercase English letters.
The length of is an odd number between and (inclusive).
Input
Input is given from Standard Input in the following format:
Output
If is a strong palindrome, print Yes
; otherwise, print No
.
Sample Input 1
akasaka
Sample Output 1
Yes
is akasaka
.
The string formed by the -st through the -rd characters is aka
.
The string formed by the -th through the -th characters is aka
. All of these are palindromes, so is a strong palindrome.
Sample Input 2
level
Sample Output 2
No
Sample Input 3
atcoder
Sample Output 3
No
Translation
给一个字符串,要求判断该字符串是不是(条件见英文题面)。
Idea
按题给意思模拟。
用函数判断是否回文。
Code
1 |
|
C - Maximum Volume
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : points
Problem Statement
Given is a positive integer . Find the maximum possible volume of a rectangular cuboid whose sum of the dimensions (not necessarily integers) is .
Constraints
is an integer.
Input
Input is given from Standard Input in the following format:
Output
Print the maximum possible volume of a rectangular cuboid whose sum of the dimensions (not necessarily integers) is . Your output is considered correct if its absolute or relative error from our answer is at most .
Sample Input 1
3
Sample Output 1
1.000000000000
For example, a rectangular cuboid whose dimensions are , , and has a volume of .
On the other hand, if the dimensions are , , and , the volume of the rectangular cuboid is , which is greater.
Sample Input 2
999
Sample Output 2
36926037.000000000000
Translation
长方体的长、宽、高之和为,问其最大体积。
Idea
由不等式,$\sqrt[n]{\prod\limits_{i=1}^{n}x_i}\leqslant \frac{\sum\limits_{i=1}^{n}x_i}{n}$,当且仅当时取等号。
故$V_{max}=\frac{L}{3}\times\frac{L}{3}\times\frac{L}{3}=\frac{L^3}{27}$。
Code
1 |
|
D - Banned K
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : points
Problem Statement
We have balls. The -th ball has an integer written on it.
For each , solve the following problem and print the answer.
Find the number of ways to choose two distinct balls (disregarding order) from the balls other than the -th ball so that the integers written on them are equal.
Constraints
All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
For each , print a line containing the answer.
Sample Input 1
5
1 1 2 1 2
Sample Output 1
2
2
3
2
3
Consider the case for example. The numbers written on the remaining balls are.
From these balls, there are two ways to choose two distinct balls so that the integers written on them are equal.
Thus, the answer for is .
Sample Input 2
4
1 2 3 4
Sample Output 2
0
0
0
0
No two balls have equal numbers written on them.
Sample Input 3
5
3 3 3 3 3
Sample Output 3
6
6
6
6
6
Any two balls have equal numbers written on them.
Sample Input 4
8
1 2 1 4 2 1 4 1
Sample Output 4
5
7
5
7
7
5
7
5
Translation
给个球,第个球上印着数字。对于每一个,要在剩余个数字中选出两个相同的数字;要求对于每一个,输出方案数。
Idea
如果要计算从个数中选取两个相同数字的方案,就相当简单,只需要计算每一个数字出现的次数,答案即为。这里的组合数,每种数字应该只计算一次,否则会有冗余,当一个计算过的数字再次遍历到时应当跳过。
对于每一个,每次将剩余个数扫一遍显然会,可以利用的思想,采取加减贡献的策略。
Code
1 |
|
E - Dividing Chocolate
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : points
Problem Statement
We have a chocolate bar partitioned into horizontal rows and vertical columns of squares.
The square at the i-th row from the top and the -th column from the left is dark if is and white if is .
We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.
How many times do we need to cut the bar so that every block after the cuts has or less white squares?
Constraints
is or .
Input
Input is given from Standard Input in the following format:
Output
Print the number of minimum times the bar needs to be cut so that every block after the cuts has or less white squares.
Sample Input 1
3 5 4
11100
10001
00111
Sample Output 1
2
For example, cutting between the -st and -nd rows and between the -rd and -th columns - as shown in the figure to the left - works.
Note that we cannot cut the bar in the ways shown in the two figures to the right.
Sample Input 2
3 5 8
11100
10001
00111
Sample Output 2
0
No cut is needed.
Sample Input 3
4 10 4
1110010010
1000101110
0011101001
1101000111
Sample Output 3
3
Translation
给定一个的01
字符矩阵。求最少需要多少次水平或竖直切割,使得切出的每一块都包含不超过个1
。
Idea
的范围很小,可以枚举种水平切割情况,竖直切割情况则用贪心策略检验。
对于每一种水平切割的方案,按列从左往右贪心,每到一列,水平切割切成的每一块当前的1
的个数就会增加该列1
的个数,如果至少有一块当前的1
的个数超过了,便在本列与上一列之间竖直切割一刀,如果仍然超过,那么此种水平切割方案就不可行。对于每种水平切割状态,如果可行就需要更新答案。
时间复杂度。
Code
1 |
|
Postscipt
一个数据规模较小的维度用二进制压缩枚举,另一个数据规模较大的维度进行贪心策略。
F - Knapsack for All Segments
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : points
Problem Statement
Given are a sequence of integers and a positive integer .
For a pair of integers such that , let us define as follows:
is the number of sequences of integers such that and .
Find the sum of over all pairs of integers such that . Since this sum can be enormous, print it modulo .
Constraints
All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the sum of , modulo .
Sample Input 1
3 4
2 2 4
Sample Output 1
5
The value of for each pair is as follows, for a total of .
(for the sequence )
(for and )
(for )
(for )
Sample Input 2
5 8
9 9 9 9 9
Sample Output 2
0
Sample Input 3
10 10
3 1 4 1 5 9 2 6 5 3
Sample Output 3
152
Translation
给定一个长度为 的数组 和一个正整数 ,定义 为原数组中满足: 并且 的子序列数量。求 。
Idea
表示当前和为 的子序列数量,那么本题的方案数就可以通过 背包的方法转移。考虑新加入一个数字 时的转移,首先对于新加入的元素,我们只需要考虑新加入元素与先前元素构成的新子序列,即只考虑 右端点变化,这一过程通过 背包转移方案数;然后, 左端点的选择是在 范围内任意的,因此加入的 对后继的影响是: 。
Code
1 |
|
Postscrip
很多动态规划问题都可以转化为背包模型。