AtCoder Beginner Contest 047

A - キャンディーと2人の子供

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

競プロ幼稚園に通う 2 人の子供がキャンディーの取り合いをしています。

3 個のキャンディーパックがあり、それぞれのパックにはキャンディーが a, b, c 個入っています。

えび先生はこの 3 個のパックを、キャンディーの個数が等しくなるように 2 人に分けようとしています。そのような分け方が可能かどうかを判定してください。

ただし、キャンディーをパックから取り出すことはできず、それぞれのパックをそのままどちらかの子供にあげる必要があります。

制約

1 ≦ a, b, c ≦ 100

入力

入力は以下の形式で標準入力から与えられる。

a b c

出力

キャンディーを同じ個数に分けられるなら Yes を、そうでなければ No を出力せよ。

入力例 1

10 30 20

出力例 1

Yes

ひとりめの子供に 30 個のキャンディーの入ったパックを、もう一方の子供に 10 個と 20 個のキャンディーの入ったパックをあげると、2 人のもらうキャンディーの個数を等しくすることができます。

入力例 2

30 30 100

出力例 2

No

この場合、100 個のキャンディーの入ったパックを貰った子供は必ずもう一方の子供より多くのキャンディーを貰うことになってしまいます。

3 つすべてのパックをどちらかの子供にあげるように分けなければならないことに注意してください。

入力例 3

56 25 31

出力例 3

Yes

Score : 100 points

Problem Statement

Two students of AtCoder Kindergarten are fighting over candy packs.

There are three candy packs, each of which contains a, b, and c candies, respectively.

Teacher Evi is trying to distribute the packs between the two students so that each student gets the same number of candies. Determine whether it is possible.

Note that Evi cannot take candies out of the packs, and the whole contents of each pack must be given to one of the students.

Constraints

1 ≦ a, b, c ≦ 100

Input

The input is given from Standard Input in the following format:

a b c

Output

If it is possible to distribute the packs so that each student gets the same number of candies, print Yes. Otherwise, print No.

Sample Input 1

10 30 20

Sample Output 1

Yes

Give the pack with 30 candies to one student, and give the two packs with 10 and 20 candies to the other. Then, each gets 30 candies.

Sample Input 2

30 30 100

Sample Output 2

No

In this case, the student who gets the pack with 100 candies always has more candies than the other.

Note that every pack must be given to one of them.

Sample Input 3

56 25 31

Sample Output 3

Yes

B - すぬけ君の塗り絵 2 イージー

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 200 点

問題文

xy 平面上に、左下の座標が (0, 0)、右上の座標が (W, H) で、各辺が x 軸か y 軸に平行な長方形があります。最初、長方形の内部は白く塗られています。

すぬけ君はこの長方形の中に N 個の点を打ちました。i 個目 (1 ≦ i ≦ N) 点の座標は (x_i, y_i) でした。

また、すぬけ君は長さ N の数列 a を決めて、各 1 ≦ i ≦ N に対し、

a_i = 1 のときは長方形の x < x_i をみたす領域
a_i = 2 のときは長方形の x > x_i をみたす領域
a_i = 3 のときは長方形の y < y_i をみたす領域
a_i = 4 のときは長方形の y > y_i をみたす領域

を黒く塗りました。

塗りつぶしが終わったあとの長方形内での白い部分の面積を求めてください。

制約

1 ≦ W, H ≦ 100
1 ≦ N ≦ 100
0 ≦ x_i ≦ W (1 ≦ i ≦ N)
0 ≦ y_i ≦ H (1 ≦ i ≦ N)
W, H (21:32 追記), x_i, y_i は整数である
a_i (1 ≦ i ≦ N) は 1, 2, 3, 4 のいずれかである

入力

入力は以下の形式で標準入力から与えられる。

W H N
x_1 y_1 a_1
x_2 y_2 a_2
:
x_N y_N a_N

出力

塗りつぶしが終わったあとの長方形内での白い部分の面積を出力せよ。

入力例 1

5 4 2
2 1 1
3 3 4

出力例 1

すぬけ君が塗りつぶしを始める前の長方形は以下の図のようになっています。

(x_1, y_1) = (2, 1)、a_1 = 1 なので、まずすぬけ君は x 座標が 2 より小さい領域を塗りつぶし、長方形は以下のようになります。

(x_2, y_2) = (3, 3)、a_2 = 4 なので、次にすぬけ君は y 座標が 3 より大きい領域を塗りつぶし、長方形は最終的に以下のようになります。

この最終的な状態における白い部分の面積は 9 なので、出力は 9 となります。

入力例 2

出力例 2

塗りつぶした結果、白い部分が残らないこともありえます。

入力例 3

出力例 3

Score : 200 points

Problem Statement

There is a rectangle in the xy-plane, with its lower left corner at (0, 0) and its upper right corner at (W, H). Each of its sides is parallel to the x-axis or y-axis. Initially, the whole region within the rectangle is painted white.

Snuke plotted N points into the rectangle. The coordinate of the i-th (1 ≦ i ≦ N) point was (x_i, y_i).

Then, he created an integer sequence a of length N, and for each 1 ≦ i ≦ N, he painted some region within the rectangle black, as follows:

If a_i = 1, he painted the region satisfying x < x_i within the rectangle.
If a_i = 2, he painted the region satisfying x > x_i within the rectangle.
If a_i = 3, he painted the region satisfying y < y_i within the rectangle.
If a_i = 4, he painted the region satisfying y > y_i within the rectangle.

Find the area of the white region within the rectangle after he finished painting.

Constraints

1 ≦ W, H ≦ 100
1 ≦ N ≦ 100
0 ≦ x_i ≦ W (1 ≦ i ≦ N)
0 ≦ y_i ≦ H (1 ≦ i ≦ N)
W, H (21:32, added), x_i and y_i are integers.
a_i (1 ≦ i ≦ N) is 1, 2, 3 or 4.

Input

The input is given from Standard Input in the following format:

W H N
x_1 y_1 a_1
x_2 y_2 a_2
:
x_N y_N a_N

Output

Print the area of the white region within the rectangle after Snuke finished painting.

Sample Input 1

5 4 2
2 1 1
3 3 4

Sample Output 1

The figure below shows the rectangle before Snuke starts painting.

First, as (x_1, y_1) = (2, 1) and a_1 = 1, he paints the region satisfying x < 2 within the rectangle:

Then, as (x_2, y_2) = (3, 3) and a_2 = 4, he paints the region satisfying y > 3 within the rectangle:

Now, the area of the white region within the rectangle is 9.

Sample Input 2

Sample Output 2

It is possible that the whole region within the rectangle is painted black.

Sample Input 3

Sample Output 3

C - 一次元リバーシ

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 300 点

問題文

きつねの次郎と三郎が一次元リバーシで遊んでいます。一次元リバーシでは、盤面には白か黒の石が一列に並んだ状態となっており、列の右端か左端に新たに石を打っていきます。通常のリバーシと同じように、たとえば白の石を打つことで黒の石を挟むと、挟まれた黒の石は白い石に変わります。

ゲームの途中で三郎に急用ができて帰ってしまうことになりました。このとき、盤面の状態は文字列 S で表されます。石は |S| (文字列の長さ) 個並んでおり、左から i (1 ≦ i ≦ |S|) 個目の石の色は、S の i 文字目が B のとき黒、W のとき白です。

次郎は現在の盤面に対して、できるだけ少ない個数の石を新たに打つことで全ての石を同じ色にしようと考えました。最小で何個の石を打てばよいかを求めてください。

制約

1 ≦ |S| ≦ 10^5
S に含まれる文字は B または W のいずれかである

入力

入力は以下の形式で標準入力から与えられる。

出力

全ての石を同じ色にするために打つ必要のある石の個数の最小値を出力せよ。

入力例 1

BBBWW

出力例 1

たとえば右端に黒い石を打つとすべての白い石を黒い石にすることができます。他にも、左端に白い石を打つことでもすべての石の色を同じにできます。

いずれの場合も 1 個の石ですべての石を同じ色にすることができるので、1 を出力します。

入力例 2

WWWWWW

出力例 2

最初から全ての石が同じ色の場合、新たに石を打つ必要はありません。

入力例 3

WBWBWBWBWB

出力例 3

Score : 300 points

Problem Statement

Two foxes Jiro and Saburo are playing a game called 1D Reversi. This game is played on a board, using black and white stones. On the board, stones are placed in a row, and each player places a new stone to either end of the row. Similarly to the original game of Reversi, when a white stone is placed, all black stones between the new white stone and another white stone, turn into white stones, and vice versa.

In the middle of a game, something came up and Saburo has to leave the game. The state of the board at this point is described by a string S. There are |S| (the length of S) stones on the board, and each character in S represents the color of the i-th (1 ≦ i ≦ |S|) stone from the left. If the i-th character in S is B, it means that the color of the corresponding stone on the board is black. Similarly, if the i-th character in S is W, it means that the color of the corresponding stone is white.

Jiro wants all stones on the board to be of the same color. For this purpose, he will place new stones on the board according to the rules. Find the minimum number of new stones that he needs to place.

Constraints

1 ≦ |S| ≦ 10^5
Each character in S is B or W.

Input

The input is given from Standard Input in the following format:

Output

Print the minimum number of new stones that Jiro needs to place for his purpose.

Sample Input 1

BBBWW

Sample Output 1

By placing a new black stone to the right end of the row of stones, all white stones will become black. Also, by placing a new white stone to the left end of the row of stones, all black stones will become white.

In either way, Jiro's purpose can be achieved by placing one stone.

Sample Input 2

WWWWWW

Sample Output 2

If all stones are already of the same color, no new stone is necessary.

Sample Input 3

WBWBWBWBWB

Sample Output 3

D - 高橋君と見えざる手

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 400 点

問題文

N 個の町が一直線上に並んでいます。行商人の高橋君は町 1 から出発し、リンゴの売買をしながら町 N へと向かいます。

はじめ高橋君は町 1 におり、リンゴを 1 つも持っていません。高橋君は次のいずれかの行動を繰り返し行います。

移動: 町 i (i < N) にいるとき、町 i + 1 へ移動する。
リンゴの売買: リンゴを好きな個数だけ売買する。ここで、町 i (1 ≦ i ≦ N) ではリンゴの買値も売値もともに A_i 円とする。ここで A_i は相異なる整数です。

1 つの町で売買するリンゴの個数に制限はありませんが、旅の中で売買するリンゴの個数は合計で (買う個数と売る個数を合わせて) T 個以下にしなくてはなりません。

高橋君は旅の利益、すなわちリンゴを売った代金から買った代金を引いた値を最大にするように旅をするとします。旅が終わったときに持っていたリンゴの価値は考えず、旅の中で売買した金額だけを考えます。

この旅に先立って、青木君は任意の町 i に対して A_i を好きな非負整数 A_i' に変えるという操作を好きなだけ行うことができます。ただし、この操作は行うごとに |A_i - A_i'| のコストがかかります。操作後には異なる町の間でリンゴの値段が同じになっていても構いません。

青木君の目的はできるだけ少ない合計コストの操作で高橋君の利益を少なくとも 1 円下げることです。合計コストの最小値を求めてください。

ただし、元の状態で高橋君が 1 円以上の利益を上げられることは仮定して構いません。

制約

1 ≦ N ≦ 10^5
1 ≦ A_i ≦ 10^9 (1 ≦ i ≦ N)
A_i は相異なる
2 ≦ T ≦ 10^9
入力の状態では高橋君は 1 円以上の利益を上げられることが保証される

入力

入力は以下の形式で標準入力から与えられる。

N T
A_1 A_2 ... A_N

出力

高橋君の収益を少なくとも 1 円下げるために必要な合計コストの最小値を出力せよ。

入力例 1

3 2
100 50 200

出力例 1

この入力の状態では、高橋君は次のようにして最大の利益である 150 円を達成することができます。

町 1 から町 2 へ移動する。
町 2 で 50 円を支払い、リンゴを 1 個買う。
町 2 から町 3 へ移動する。
町 3 で 200 円でリンゴを 1 個売る。

たとえば、青木君が町 2 のリンゴの値段を 50 円から 51 円に変えると、高橋君はどのようにしても 150 円の利益を上げることができなくなります。すなわち、コスト 1 で高橋君の利益を少なくとも 1 円下げることが可能であり、答えは 1 となります。

他にも、町 3 のリンゴの値段を 200 円から 199 円に変えることでもコスト 1 で高橋君の利益を下げることが可能です。

入力例 2

5 8
50 30 40 10 20

出力例 2

入力例 3

10 100
7 10 4 5 9 3 6 8 2 1

出力例 3

Score : 400 points

Problem Statement

There are N towns located in a line, conveniently numbered 1 through N. Takahashi the merchant is going on a travel from town 1 to town N, buying and selling apples.

Takahashi will begin the travel at town 1, with no apple in his possession. The actions that can be performed during the travel are as follows:

Move: When at town i (i < N), move to town i + 1.
Merchandise: Buy or sell an arbitrary number of apples at the current town. Here, it is assumed that one apple can always be bought and sold for A_i yen (the currency of Japan) at town i (1 ≦ i ≦ N), where A_i are distinct integers. Also, you can assume that he has an infinite supply of money.

For some reason, there is a constraint on merchandising apple during the travel: the sum of the number of apples bought and the number of apples sold during the whole travel, must be at most T. (Note that a single apple can be counted in both.)

During the travel, Takahashi will perform actions so that the profit of the travel is maximized. Here, the profit of the travel is the amount of money that is gained by selling apples, minus the amount of money that is spent on buying apples. Note that we are not interested in apples in his possession at the end of the travel.

Aoki, a business rival of Takahashi, wants to trouble Takahashi by manipulating the market price of apples. Prior to the beginning of Takahashi's travel, Aoki can change A_i into another arbitrary non-negative integer A_i' for any town i, any number of times. The cost of performing this operation is |A_i - A_i'|. After performing this operation, different towns may have equal values of A_i.

Aoki's objective is to decrease Takahashi's expected profit by at least 1 yen. Find the minimum total cost to achieve it. You may assume that Takahashi's expected profit is initially at least 1 yen.

Constraints

1 ≦ N ≦ 10^5
1 ≦ A_i ≦ 10^9 (1 ≦ i ≦ N)
A_i are distinct.
2 ≦ T ≦ 10^9
In the initial state, Takahashi's expected profit is at least 1 yen.

Input

The input is given from Standard Input in the following format:

N T
A_1 A_2 ... A_N

Output

Print the minimum total cost to decrease Takahashi's expected profit by at least 1 yen.

Sample Input 1

3 2
100 50 200

Sample Output 1

In the initial state, Takahashi can achieve the maximum profit of 150 yen as follows:

Move from town 1 to town 2.
Buy one apple for 50 yen at town 2.
Move from town 2 to town 3.
Sell one apple for 200 yen at town 3.

If, for example, Aoki changes the price of an apple at town 2 from 50 yen to 51 yen, Takahashi will not be able to achieve the profit of 150 yen. The cost of performing this operation is 1, thus the answer is 1.

There are other ways to decrease Takahashi's expected profit, such as changing the price of an apple at town 3 from 200 yen to 199 yen.

Sample Input 2

5 8
50 30 40 10 20

Sample Output 2

Sample Input 3

10 100
7 10 4 5 9 3 6 8 2 1