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 の市松模様の例です。

cba927b2484fad94fb5ff7473e9aadef.png

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

4 3
0 1 W
1 2 W
5 3 B
5 4 B

出力例 1

4

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

入力例 2

2 1000
0 0 B
0 1 W

出力例 2

2

入力例 3

6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W

出力例 3

4

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:

cba927b2484fad94fb5ff7473e9aadef.png

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

4 3
0 1 W
1 2 W
5 3 B
5 4 B

Sample Output 1

4

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

2

Sample Input 3

6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W

Sample Output 3

4
E - GraphXY

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 900 点

問題文

シカのAtCoDeerくんは次のような条件を満たす有向グラフを欲しがっています。

  • 頂点数Nは 300 以下
  • 自己ループや多重辺があってはいけない
  • 頂点には 1 から N の番号が付けられている
  • 各辺には 0 以上 100 以下の整数値の重み、もしくは、X または Y というラベルが付けられている
  • 全ての 1 ≤ x ≤ A, 1 ≤ y ≤ B, を満たす整数の組 (x,y) に対し、 ラベル X が付けられた辺の重みを x に、 Y が付けられた辺の重みを y に書き換えたグラフの 頂点 S から T への最短距離は d_{x,y}

AtCoDeerくんのためにこのようなグラフ(と S と T の組)をひとつ構成してください。条件を満たすグラフが存在しない場合はそれを指摘してください。 出力の方法については出力の欄を参照してください。

制約

  • 1 ≤ A,B ≤ 10
  • 1 ≤ d_{x,y} ≤ 100 (1 ≤ x ≤ A, 1 ≤ y ≤ B)
  • 入力は全て整数

入力

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

A B
d_{1,1} d_{1,2} .. d_{1,B}
d_{2,1} d_{2,2} .. d_{2,B}
:
d_{A,1} d_{A,2} .. d_{A,B}

出力

条件を満たすグラフが存在しない場合は Impossible と出力せよ。

条件を満たすグラフが存在する場合、 1 行目に Possible と出力せよ。 2行目以降に 構成したグラフを以下の形式で標準出力に出力せよ。

N M
u_1 v_1 c_1
u_2 v_2 c_2
:
u_M v_M c_M
S T

ただし、 M は出力するグラフの辺数、 u_i,v_i,c_i はグラフの辺を表す。 これは頂点 u_i から 頂点 v_i に 重み、あるいはラベル c_i の有向辺があることを意味する。 入出力例も参考にせよ。

入力例 1

2 3
1 2 2
1 2 3

出力例 1

Possible
3 4
1 2 X
2 3 1
3 2 Y
1 3 Y
1 3

入力例 2

1 3
100 50 1

出力例 2

Impossible

Score : 900 points

Problem Statement

AtCoDeer the deer wants a directed graph that satisfies the following conditions:

  • The number of vertices, N, is at most 300.
  • There must not be self-loops or multiple edges.
  • The vertices are numbered from 1 through N.
  • Each edge has either an integer weight between 0 and 100 (inclusive), or a label X or Y.
  • For every pair of two integers (x,y) such that 1 ≤ x ≤ A, 1 ≤ y ≤ B, the shortest distance from Vertex S to Vertex T in the graph where the edges labeled X have the weight x and the edges labeled Y have the weight y, is d_{x,y}.

Construct such a graph (and a pair of S and T) for him, or report that it does not exist. Refer to Output section for output format.

Constraints

  • 1 ≤ A,B ≤ 10
  • 1 ≤ d_{x,y} ≤ 100 (1 ≤ x ≤ A, 1 ≤ y ≤ B)
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

A B
d_{1,1} d_{1,2} .. d_{1,B}
d_{2,1} d_{2,2} .. d_{2,B}
:
d_{A,1} d_{A,2} .. d_{A,B}

Output

If no graph satisfies the condition, print Impossible.

If there exists a graph that satisfies the condition, print Possible in the first line. Then, in the subsequent lines, print the constructed graph in the following format:

N M
u_1 v_1 c_1
u_2 v_2 c_2
:
u_M v_M c_M
S T

Here, M is the number of the edges, and u_i, v_i, c_i represent edges as follows: there is an edge from Vertex u_i to Vertex v_i whose weight or label is c_i.

Also refer to Sample Outputs.

Sample Input 1

2 3
1 2 2
1 2 3

Sample Output 1

Possible
3 4
1 2 X
2 3 1
3 2 Y
1 3 Y
1 3

Sample Input 2

1 3
100 50 1

Sample Output 2

Impossible
F - ColoringBalls

Time Limit: 4 sec / Memory Limit: 256 MB

配点 : 1100 点

問題文

1,2,..,N の番号のついた N 個の白いボールがこの順に一列に並んでいます。 シカのAtCoDeerくんはこれらのボールに赤と青で色を塗りたいと考えています。 ただし、最終的に白のままのボールがある可能性もあります。

長さ K の文字列 s が与えられます。 AtCoDeerくんは i=1 から i=K まで順に次の操作を行います。

  • i 番目の操作: 連続するボールの区間(空でもよい)を一つ選んで、s の i 文字目が r なら赤で、 b なら青でそのボール達を塗る

ただし、既に色が塗られているボールに再度色を塗った場合、色は上書きされます。 また、塗料の都合上 まだ色が塗られていない白いボールを直接青で塗ることはできません。 すなわち、s の i 文字目が b のとき、白いボールを含む区間を選ぶことはできません。

すべての操作が終わったあとにありうるボールの色の列が何通りありうるか求めてください。 答えは大きくなる可能性があるので、 10^9+7 で割ったあまりを求めてください。

制約

  • 1 ≤ N ≤ 70
  • 1 ≤ K ≤ 70
  • |s| = K
  • s は r か b のみからなる
  • N,K は整数

入力

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

N K
s

出力

すべての操作が終わったあとにありうるボールの色の列が何通りあるかを 10^9+7 で割ったあまりを出力せよ。

入力例 1

2 2
rb

出力例 1

9

赤をr,青をb,白をwで表すと、最終的にあり得るボールの列は次の 9 通りです。

ww, wr, rw, rr, wb, bw, bb, rb, br

入力例 2

5 2
br

出力例 2

16

白いボールに直接青を塗ることは出来ないので、 1 回目の操作では空の区間を選ぶしかありません。

入力例 3

7 4
rbrb

出力例 3

1569

入力例 4

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

出力例 4

841634130

Score : 1100 points

Problem Statement

There are N white balls arranged in a row, numbered 1,2,..,N from left to right. AtCoDeer the deer is thinking of painting some of these balls red and blue, while leaving some of them white.

You are given a string s of length K. AtCoDeer performs the following operation for each i from 1 through K in order:

  • The i-th operation: Choose a contiguous segment of balls (possibly empty), and paint these balls red if the i-th character in s is r; paint them blue if the character is b.

Here, if a ball which is already painted is again painted, the color of the ball will be overwritten. However, due to the properties of dyes, it is not possible to paint a white, unpainted ball directly in blue. That is, when the i-th character in s is b, the chosen segment must not contain a white ball.

After all the operations, how many different sequences of colors of the balls are possible? Since the count can be large, find it modulo 10^9+7.

Constraints

  • 1 ≤ N ≤ 70
  • 1 ≤ K ≤ 70
  • |s| = K
  • s consists of r and b.
  • N and K are integers.

Input

Input is given from Standard Input in the following format:

N K
s

Output

Print the number of the different possible sequences of colors of the balls after all the operations, modulo 10^9+7.

Sample Input 1

2 2
rb

Sample Output 1

9

There are nine possible sequences of colors of the balls, as follows:

ww, wr, rw, rr, wb, bw, bb, rb, br.

Here, r represents red, b represents blue and wrepresents white.

Sample Input 2

5 2
br

Sample Output 2

16

Since we cannot directly paint white balls in blue, we can only choose an empty segment in the first operation.

Sample Input 3

7 4
rbrb

Sample Output 3

1569

Sample Input 4

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

Sample Output 4

841634130