A - Buttons

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

2 個のボタンがあり、大きさはそれぞれ A, B です。

あなたは、いずれかのボタンを押すことを 2 回行います。 同じボタンを 2 回押しても構いません。

### 制約

• 入力は全て整数である。
• 3 \leq A, B \leq 20

### 入力

A B


### 入力例 1

5 3


### 出力例 1

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

B - Great Ocean View

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

これら 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


### 入力例 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

C - Coloring Colorfully

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

あなたは、いくつかのタイルを黒色または白色に塗り替えることで、どの隣り合う 2 枚のタイルも異なる色で塗られているようにしたいです。

### 制約

• 1 \leq |S| \leq 10^5
• S_i0 または 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 or 1.

### 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

D - Handstand

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 人の人が左右一列に並んでいます。

0, 1 からなる長さ N の文字列 S と正整数 K が与えられます。

あなたは K 回まで以下の指示を行います。一度も行わなくても構いません。

K 回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか求めてください。

### 制約

• N1 \leq N \leq 10^5 を満たす整数である。
• K1 \leq K \leq 10^5 を満たす整数である。
• 文字列 S の長さは N である。
• 文字列 S の各文字は 0 または 1 である。

### 入力

N K
S


### 出力

K 回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか出力せよ。

### 入力例 1

5 1
00010


### 出力例 1

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 or 1.

### 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.