Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
2 個のボタンがあり、大きさはそれぞれ A, B です。
大きさ X のボタンを押すと、X 枚のコインを獲得し、そのボタンの大きさが 1 小さくなります。
あなたは、いずれかのボタンを押すことを 2 回行います。 同じボタンを 2 回押しても構いません。
最大で何枚のコインを獲得できるでしょうか。
制約
- 入力は全て整数である。
- 3 \leq A, B \leq 20
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
獲得できるコインの枚数の最大値を出力せよ。
入力例 1
5 3
出力例 1
9
大きさ 5 のボタンを 2 回押すと 5 + 4 = 9 枚のコインが獲得でき、これが最大です。
入力例 2
3 4
出力例 2
7
入力例 3
6 6
出力例 3
12
Score : 100 points
Problem Statement
There are two buttons, one of size A and one of size B.
When you press a button of size X, you get X coins and the size of that button decreases by 1.
You will press a button twice. Here, you can press the same button twice, or press both buttons once.
At most how many coins can you get?
Constraints
- All values in input are integers.
- 3 \leq A, B \leq 20
Input
Input is given from Standard Input in the following format:
A B
Output
Print the maximum number of coins you can get.
Sample Input 1
5 3
Sample Output 1
9
You can get 5 + 4 = 9 coins by pressing the button of size 5 twice, and this is the maximum result.
Sample Input 2
3 4
Sample Output 2
7
Sample Input 3
6 6
Sample Output 3
12
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
東西に N 個の山が連なっており、西の果てには広大な海が広がっています。
各山頂には旅館があり、あなたは海を眺められる旅館を選ぶことにしました。
西から i 番目の山の高さは H_i です。
西から 1 番目の山頂にある旅館からは必ず海を眺めることができます。
西から i (i = 2, 3, ..., N) 番目の山頂にある旅館については、H_1 \leq H_i, H_2 \leq H_i, ..., かつ H_{i-1} \leq H_i のとき、その旅館から海を眺めることができます。
これら N 個の旅館のうち、海を眺められる旅館はいくつあるでしょうか。
制約
- 入力は全て整数である。
- 1 \leq N \leq 20
- 1 \leq H_i \leq 100
入力
入力は以下の形式で標準入力から与えられる。
N H_1 H_2 ... H_N
出力
海を眺められる旅館の数を出力せよ。
入力例 1
4 6 5 6 8
出力例 1
3
西から 1, 3, 4 番目の旅館から海を眺めることができます。
入力例 2
5 4 5 3 5 4
出力例 2
3
入力例 3
5 9 5 6 8 4
出力例 3
1
Score : 200 points
Problem Statement
There are N mountains ranging from east to west, and an ocean to the west.
At the top of each mountain, there is an inn. You have decided to choose where to stay from these inns.
The height of the i-th mountain from the west is H_i.
You can certainly see the ocean from the inn at the top of the westmost mountain.
For the inn at the top of the i-th mountain from the west (i = 2, 3, ..., N), you can see the ocean if and only if H_1 \leq H_i, H_2 \leq H_i, ..., and H_{i-1} \leq H_i.
From how many of these N inns can you see the ocean?
Constraints
- All values in input are integers.
- 1 \leq N \leq 20
- 1 \leq H_i \leq 100
Input
Input is given from Standard Input in the following format:
N H_1 H_2 ... H_N
Output
Print the number of inns from which you can see the ocean.
Sample Input 1
4 6 5 6 8
Sample Output 1
3
You can see the ocean from the first, third and fourth inns from the west.
Sample Input 2
5 4 5 3 5 4
Sample Output 2
3
Sample Input 3
5 9 5 6 8 4
Sample Output 3
1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
左右一列に N 枚のタイルが並んでおり、各タイルの初めの色は長さ N の文字列 S で表されます。
左から i 番目のタイルは、S の i 番目の文字が 0
のとき黒色で、1
のとき白色で塗られています。
あなたは、いくつかのタイルを黒色または白色に塗り替えることで、どの隣り合う 2 枚のタイルも異なる色で塗られているようにしたいです。
最小で何枚のタイルを塗り替えることで条件を満たすようにできるでしょうか。
制約
- 1 \leq |S| \leq 10^5
- S_i は
0
または1
である。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
条件を満たすために塗り替えるタイルの枚数の最小値を出力せよ。
入力例 1
000
出力例 1
1
中央のタイルを白色に塗り替えれば条件を達成できます。
入力例 2
10010010
出力例 2
3
入力例 3
0
出力例 3
0
Score : 300 points
Problem Statement
N tiles are arranged in a row from left to right. The initial color of each tile is represented by a string S of length N.
The i-th tile from the left is painted black if the i-th character of S is 0
, and painted white if that character is 1
.
You want to repaint some of the tiles black or white, so that any two adjacent tiles have different colors.
At least how many tiles need to be repainted to satisfy the condition?
Constraints
- 1 \leq |S| \leq 10^5
- S_i is
0
or1
.
Input
Input is given from Standard Input in the following format:
S
Output
Print the minimum number of tiles that need to be repainted to satisfy the condition.
Sample Input 1
000
Sample Output 1
1
The condition can be satisfied by repainting the middle tile white.
Sample Input 2
10010010
Sample Output 2
3
Sample Input 3
0
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 人の人が左右一列に並んでいます。
0
, 1
からなる長さ N の文字列 S と正整数 K が与えられます。
左から i 番目の人は、S の i 文字目が 0
のとき直立し、1
のとき逆立ちしています。
あなたは K 回まで以下の指示を行います。一度も行わなくても構いません。
指示: 1 \leq l \leq r \leq N を満たす整数 l, r を選ぶ。左から l, l+1, ..., r 番目の人の状態を反転する。すなわち、i = l, l+1, ..., r について、左から i 番目の人は直立していれば逆立ちし、逆立ちしていれば直立する。
K 回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか求めてください。
制約
- N は 1 \leq N \leq 10^5 を満たす整数である。
- K は 1 \leq K \leq 10^5 を満たす整数である。
- 文字列 S の長さは N である。
- 文字列 S の各文字は
0
または1
である。
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
K 回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか出力せよ。
入力例 1
5 1 00010
出力例 1
4
以下のように指示を行えば逆立ちした人を連続して 4 人並ばせることができ、これが最大です。
- l = 1, r = 3 として指示を行う。その結果、左から 1, 2, 3 番目の人の状態が反転する。
入力例 2
14 2 11101010110011
出力例 2
8
入力例 3
1 1 1
出力例 3
1
一度も指示を行う必要はありません。
Score : 400 points
Problem Statement
N people are arranged in a row from left to right.
You are given a string S of length N consisting of 0
and 1
, and a positive integer K.
The i-th person from the left is standing on feet if the i-th character of S is 0
, and standing on hands if that character is 1
.
You will give the following direction at most K times (possibly zero):
Direction: Choose integers l and r satisfying 1 \leq l \leq r \leq N, and flip the l-th, (l+1)-th, ..., and r-th persons. That is, for each i = l, l+1, ..., r, the i-th person from the left now stands on hands if he/she was standing on feet, and stands on feet if he/she was standing on hands.
Find the maximum possible number of consecutive people standing on hands after at most K directions.
Constraints
- N is an integer satisfying 1 \leq N \leq 10^5.
- K is an integer satisfying 1 \leq K \leq 10^5.
- The length of the string S is N.
- Each character of the string S is
0
or1
.
Input
Input is given from Standard Input in the following format:
N K S
Output
Print the maximum possible number of consecutive people standing on hands after at most K directions.
Sample Input 1
5 1 00010
Sample Output 1
4
We can have four consecutive people standing on hands, which is the maximum result, by giving the following direction:
- Give the direction with l = 1, r = 3, which flips the first, second and third persons from the left.
Sample Input 2
14 2 11101010110011
Sample Output 2
8
Sample Input 3
1 1 1
Sample Output 3
1
No directions are necessary.