AtCoder Beginner Contest 086

A - Product

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

シカのAtCoDeerくんは二つの正整数 a,b を見つけました。 a と b の積が偶数か奇数か判定してください。

制約

1 ≤ a,b ≤ 10000
a,b は整数

入力

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

a b

出力

積が奇数なら Odd と、偶数なら Even と出力せよ。

入力例 1

3 4

出力例 1

Even

3 × 4 = 12 は偶数なので Even を出力してください。

入力例 2

1 21

出力例 2

Odd

1 × 21 = 21 は奇数なので Odd を出力してください。

Score : 100 points

Problem Statement

AtCoDeer the deer found two positive integers, a and b. Determine whether the product of a and b is even or odd.

Constraints

1 ≤ a,b ≤ 10000
a and b are integers.

Input

Input is given from Standard Input in the following format:

a b

Output

If the product is odd, print Odd; if it is even, print Even.

Sample Input 1

3 4

Sample Output 1

Even

As 3 × 4 = 12 is even, print Even.

Sample Input 2

1 21

Sample Output 2

Odd

As 1 × 21 = 21 is odd, print Odd.

B - 1 21

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

シカのAtCoDeerくんは二つの正整数 a,b を見つけました。 a と b をこの順につなげて読んだものが平方数かどうか判定してください。

制約

1 ≤ a,b ≤ 100
a,b は整数

入力

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

a b

出力

a と b をこの順につなげて読んだものが平方数なら Yes を、そうでないなら No を出力せよ。

入力例 1

1 21

出力例 1

Yes

121 = 11 × 11 なので、平方数です。

入力例 2

100 100

出力例 2

No

100100 は平方数ではありません。

入力例 3

12 10

出力例 3

No

Score : 200 points

Problem Statement

AtCoDeer the deer has found two positive integers, a and b. Determine whether the concatenation of a and b in this order is a square number.

Constraints

1 ≤ a,b ≤ 100
a and b are integers.

Input

Input is given from Standard Input in the following format:

a b

Output

If the concatenation of a and b in this order is a square number, print Yes; otherwise, print No.

Sample Input 1

1 21

Sample Output 1

Yes

As 121 = 11 × 11, it is a square number.

Sample Input 2

100 100

Sample Output 2

No

100100 is not a square number.

Sample Input 3

12 10

Sample Output 3

No

C - Traveling

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻 t_i に点 (x_i,y_i) を訪れる予定です。

AtCoDeerくんが時刻 t に点 (x,y) にいる時、時刻 t+1 には点 (x+1,y), (x-1,y), (x,y+1), (x,y-1) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約

1 ≤ N ≤ 10^5
0 ≤ x_i ≤ 10^5
0 ≤ y_i ≤ 10^5
1 ≤ t_i ≤ 10^5
t_i < t_{i+1} (1 ≤ i ≤ N-1)
入力は全て整数

入力

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

N
t_1 x_1 y_1
t_2 x_2 y_2
:
t_N x_N y_N

出力

旅行プランが実行可能ならYesを、不可能ならNoを出力してください。

入力例 1

2
3 1 2
6 1 1

出力例 1

Yes

例えば、(0,0), (0,1), (1,1), (1,2), (1,1), (1,0), (1,1) と移動すればよいです。

入力例 2

1
2 100 100

出力例 2

No

(0,0) にいる状態から 2 秒後に (100,100) にいるのは不可能です。

入力例 3

2
5 1 1
100 1 1

出力例 3

No

Score : 300 points

Problem Statement

AtCoDeer the deer is going on a trip in a two-dimensional plane. In his plan, he will depart from point (0, 0) at time 0, then for each i between 1 and N (inclusive), he will visit point (x_i,y_i) at time t_i.

If AtCoDeer is at point (x, y) at time t, he can be at one of the following points at time t+1: (x+1,y), (x-1,y), (x,y+1) and (x,y-1). Note that he cannot stay at his place. Determine whether he can carry out his plan.

Constraints

1 ≤ N ≤ 10^5
0 ≤ x_i ≤ 10^5
0 ≤ y_i ≤ 10^5
1 ≤ t_i ≤ 10^5
t_i < t_{i+1} (1 ≤ i ≤ N-1)
All input values are integers.

Input

Input is given from Standard Input in the following format:

N
t_1 x_1 y_1
t_2 x_2 y_2
:
t_N x_N y_N

Output

If AtCoDeer can carry out his plan, print Yes; if he cannot, print No.

Sample Input 1

2
3 1 2
6 1 1

Sample Output 1

Yes

For example, he can travel as follows: (0,0), (0,1), (1,1), (1,2), (1,1), (1,0), then (1,1).

Sample Input 2

1
2 100 100

Sample Output 2

No

It is impossible to be at (100,100) two seconds after being at (0,0).

Sample Input 3

2
5 1 1
100 1 1

Sample Output 3

No

D - Checker

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500 点

問題文

シカのAtCoDeerくんは無限に広がる二次元グリッドを一辺が K の市松模様で塗ろうと考えています。ただし、一辺が K の市松模様とは、各マスが白か黒で塗られたパターンであって、各色の各連結成分が K × K の正方形となっているようなものです。例えば以下は一辺が 3 の市松模様の例です。

AtCoDeerくんは N 個の希望を持っています。 i 個目の希望は、 x_i,y_i,c_i で表されます。これは、c_i が B ならマス (x_i,y_i) を黒で塗る、 W なら白で塗ることを意味しています。同時に最大でいくつの希望を叶えることが出来るか答えてください。

制約

1 ≤ N ≤ 10^5
1 ≤ K ≤ 1000
0 ≤ x_i ≤ 10^9
0 ≤ y_i ≤ 10^9
i ≠ j なら (x_i,y_i) ≠ (x_j,y_j)
c_i は B または W
N,K,x_i,y_i は整数

入力

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

N K
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N

出力

同時に叶えられる希望の個数の最大値を出力せよ。

入力例 1

出力例 1

上であげた例のように塗ればすべての希望を同時に叶えることができます。

入力例 2

2 1000
0 0 B
0 1 W

出力例 2

入力例 3

出力例 3

Score : 500 points

Problem Statement

AtCoDeer is thinking of painting an infinite two-dimensional grid in a checked pattern of side K. Here, a checked pattern of side K is a pattern where each square is painted black or white so that each connected component of each color is a K × K square. Below is an example of a checked pattern of side 3:

AtCoDeer has N desires. The i-th desire is represented by x_i, y_i and c_i. If c_i is B, it means that he wants to paint the square (x_i,y_i) black; if c_i is W, he wants to paint the square (x_i,y_i) white. At most how many desires can he satisfy at the same time?

Constraints

1 ≤ N ≤ 10^5
1 ≤ K ≤ 1000
0 ≤ x_i ≤ 10^9
0 ≤ y_i ≤ 10^9
If i ≠ j, then (x_i,y_i) ≠ (x_j,y_j).
c_i is B or W.
N, K, x_i and y_i are integers.

Input

Input is given from Standard Input in the following format:

N K
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N

Output

Print the maximum number of desires that can be satisfied at the same time.

Sample Input 1

Sample Output 1

He can satisfy all his desires by painting as shown in the example above.

Sample Input 2

2 1000
0 0 B
0 1 W

Sample Output 2

Sample Input 3