Mujin Programming Challenge 2017

A - Robot Racing

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

配点 : 900 点

問題文

あなたはカエル型のロボットを開発しています。あなたはこのロボットに競走をさせることにしました。

まず、あなたは数直線上に N 体のロボットを置きました。ロボットには 1 から N までの番号が振られています。今、i 番目のロボットは座標 x_i にいます。ただし、x_i はすべて整数であり、0 < x_1 < x_2 < ... < x_N が成り立ちます。

あなたは次の操作を繰り返し行います。

数直線上のロボットを一体選ぶ。選んだロボットの座標を x とする。座標 x - 1, x - 2 のうち他のロボットがいない座標を着地点に選ぶ。選んだロボットを着地点へジャンプさせる。

あるロボットの座標が 0 以下になった場合、そのロボットはゴールしたと見なされ、即座に数直線から取り除かれます。すべてのロボットがゴールするまで、あなたは操作を行い続けます。

あなたが操作を行う方法によって、N 体のロボットがゴールする順番は何通りかありえます。 N 体のロボットがゴールする順番は何通りありうるでしょうか？ 10^9+7 で割った余りを求めてください。

制約

2 ≤ N ≤ 10^5
x_i は整数である。
0 < x_1 < x_2 < ... < x_N ≤ 10^9

部分点

500 点分のテストケースでは、N ≤ 8 が成り立つ。

入力

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

N
x_1 x_2 ... x_N

出力

N 体のロボットがゴールする順番は何通りありうるか？ 10^9+7 で割った余りを出力せよ。

入力例 1

3
1 2 3

出力例 1

3 体のロボットがゴールする順番は、次の 4 通りありえます。

(ロボット 1 → ロボット 2 → ロボット 3)
(ロボット 1 → ロボット 3 → ロボット 2)
(ロボット 2 → ロボット 1 → ロボット 3)
(ロボット 2 → ロボット 3 → ロボット 1)

入力例 2

3
2 3 4

出力例 2

3 体のロボットがゴールする順番は、次の 6 通りありえます。

(ロボット 1 → ロボット 2 → ロボット 3)
(ロボット 1 → ロボット 3 → ロボット 2)
(ロボット 2 → ロボット 1 → ロボット 3)
(ロボット 2 → ロボット 3 → ロボット 1)
(ロボット 3 → ロボット 1 → ロボット 2)
(ロボット 3 → ロボット 2 → ロボット 1)

例えば、次図のように操作を行うと、(ロボット 3 → ロボット 2 → ロボット 1) の順にゴールします。

入力例 3

8
1 2 3 5 7 11 13 17

出力例 3

入力例 4

13
4 6 8 9 10 12 14 15 16 18 20 21 22

出力例 4

311014372

答えを 10^9+7 で割った余りを出力してください。なお、このケースは部分点のテストケースには含まれません。

Score : 900 points

Problem Statement

You are developing frog-shaped robots, and decided to race them against each other.

First, you placed N robots onto a number line. These robots are numbered 1 through N. The current coordinate of robot i is x_i. Here, all x_i are integers, and 0 < x_1 < x_2 < ... < x_N.

You will repeatedly perform the following operation:

Select a robot on the number line. Let the coordinate of the robot be x. Select the destination coordinate, either x-1 or x-2, that is not occupied by another robot. The robot now jumps to the selected coordinate.

When the coordinate of a robot becomes 0 or less, the robot is considered finished and will be removed from the number line immediately. You will repeat the operation until all the robots finish the race.

Depending on your choice in the operation, the N robots can finish the race in different orders. In how many different orders can the N robots finish the race? Find the answer modulo 10^9+7.

Constraints

2 ≤ N ≤ 10^5
x_i is an integer.
0 < x_1 < x_2 < ... < x_N ≤ 10^9

Partial Score

In a test set worth 500 points, N ≤ 8.

Input

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

N
x_1 x_2 ... x_N

Output

Print the number of the different orders in which the N robots can finish the race, modulo 10^9+7.

Sample Input 1

3
1 2 3

Sample Output 1

There are four different orders in which the three robots can finish the race:

(Robot 1 → Robot 2 → Robot 3)
(Robot 1 → Robot 3 → Robot 2)
(Robot 2 → Robot 1 → Robot 3)
(Robot 2 → Robot 3 → Robot 1)

Sample Input 2

3
2 3 4

Sample Output 2

There are six different orders in which the three robots can finish the race:

(Robot 1 → Robot 2 → Robot 3)
(Robot 1 → Robot 3 → Robot 2)
(Robot 2 → Robot 1 → Robot 3)
(Robot 2 → Robot 3 → Robot 1)
(Robot 3 → Robot 1 → Robot 2)
(Robot 3 → Robot 2 → Robot 1)

For example, the order (Robot 3 → Robot 2 → Robot 1) can be achieved as shown in the figure below:

Sample Input 3

8
1 2 3 5 7 11 13 17

Sample Output 3

Sample Input 4

13
4 6 8 9 10 12 14 15 16 18 20 21 22

Sample Output 4

311014372

Remember to print the answer modulo 10^9+7. This case is not included in the test set for the partial score.

B - Row to Column

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

配点 : 1300 点

問題文

縦 N 行、横 N 列の正方形状のマス目があります。上から i 行目、左から j 列目のマスを (i,\ j) と表します。

最初、各マスは白か黒です。最初のマス目の配色は、正方形状に並ぶ文字 a_{ij} (1 ≤ i,\ j ≤ N) として与えられます。マス (i,\ j) が白ならば a_{ij} は . であり、黒ならば a_{ij} は # です。

あなたは、マス目の配色を塗り替えるロボットを開発しています。このロボットは次の操作を繰り返し行うことができます。

整数 i, j (1 ≤ i,\ j ≤ N) をそれぞれ自由に選ぶ。マス (i,\ 1), (i,\ 2), ..., (i,\ N) の色をそれぞれ c_1, c_2, ..., c_N として記憶する。その後、マス (1,\ j), (2,\ j), ..., (N,\ j) の色をそれぞれ c_1, c_2, ..., c_N で塗り替える。

あなたの目標は、すべてのマスを黒にすることです。すべてのマスを黒にすることが可能か判定し、可能ならば必要な操作回数の最小値を求めてください。

制約

2 ≤ N ≤ 500
a_{ij} は . または # である。

部分点

300 点分のテストケースでは、N ≤ 3 が成り立つ。

入力

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

N
a_{11}...a_{1N}
:
a_{N1}...a_{NN}

出力

すべてのマスを黒にすることが可能ならば、必要な操作回数の最小値を出力せよ。不可能ならば、代わりに -1 を出力せよ。

入力例 1

2
#.
.#

出力例 1

例えば、次のように操作を行うと、次図のようにマス目の配色が変わります。

i = 1, j = 2 と選んで操作を行う。
i = 1, j = 1 と選んで操作を行う。
i = 1, j = 2 と選んで操作を行う。

入力例 2

2
..
..

出力例 2

-1

入力例 3

2
##
##

出力例 3

入力例 4

3
.#.
###
.#.

出力例 4

入力例 5

3
...
.#.
...

出力例 5

Score : 1300 points

Problem Statement

There is a square-shaped grid with N vertical rows and N horizontal columns. We will denote the square at the i-th row from the top and the j-th column from the left as (i,\ j).

Initially, each square is either white or black. The initial color of the grid is given to you as characters a_{ij}, arranged in a square shape. If the square (i,\ j) is white, a_{ij} is .. If it is black, a_{ij} is #.

You are developing a robot that repaints the grid. It can repeatedly perform the following operation:

Select two integers i, j (1 ≤ i,\ j ≤ N). Memorize the colors of the squares (i,\ 1), (i,\ 2), ..., (i,\ N) as c_1, c_2, ..., c_N, respectively. Then, repaint the squares (1,\ j), (2,\ j), ..., (N,\ j) with the colors c_1, c_2, ..., c_N, respectively.

Your objective is to turn all the squares black. Determine whether it is possible, and find the minimum necessary number of operations to achieve it if the answer is positive.

Constraints

2 ≤ N ≤ 500
a_{ij} is either . or #.

Partial Score

In a test set worth 300 points, N ≤ 3.

Input

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

N
a_{11}...a_{1N}
:
a_{N1}...a_{NN}

Output

If it is possible to turn all the squares black, print the minimum necessary number of operations to achieve the objective. If it is impossible, print -1 instead.

Sample Input 1

2
#.
.#

Sample Output 1

For example, perform the operation as follows:

Select i = 1, j = 2.
Select i = 1, j = 1.
Select i = 1, j = 2.

The transition of the colors of the squares is shown in the figure below:

Sample Input 2

2
..
..

Sample Output 2

-1

Sample Input 3

2
##
##

Sample Output 3

Sample Input 4

3
.#.
###
.#.

Sample Output 4

Sample Input 5

3
...
.#.
...

Sample Output 5

C - Robot and String

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

配点 : 1300 点

問題文

あなたは、文字列を処理するロボットを開発しています。英小文字のみからなる文字列 t をこのロボットに与えると、ロボットは次の手順に従って文字列を処理します。

t_i = t_{i + 1} であるような最小の i を選ぶ。そのような i が存在しない場合、処理を終える。
t_i が z である場合、t_i, t_{i + 1} を取り除く。 t_i が z でない場合、t_i の次のアルファベットを c として、t_i, t_{i + 1} をまとめて1 文字の c へ置き換える。
1. へ戻る。

例えば、文字列 axxxxza をロボットに与えると、文字列は axxxxza → ayxxza → ayyza → azza → aa → b と処理されます。

英小文字のみからなる文字列 s が与えられます。 s について Q 個の質問に答えてください。 i 番目の質問は次のようなものです。

s の l_i 文字目から r_i 文字目までの連続した部分文字列をロボットに与えると、処理された後の文字列は空文字列になるか？

制約

1 ≤ |s| ≤ 5 × 10^5
s は英小文字のみからなる。
1 ≤ Q ≤ 10^5
1 ≤ l_i ≤ r_i ≤ |s|

入力

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

s
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q

出力

Q 行出力せよ。 i 行目には、i 番目の質問に対する答えとして Yes または No を出力せよ。

入力例 1

axxxxza
2
1 7
2 6

出力例 1

No
Yes

1 番目の質問では、文字列は axxxxza → ayxxza → ayyza → azza → aa → b と処理されます。
2 番目の質問では、文字列は xxxxz → yxxz → yyz → zz → と処理されます。

入力例 2

aabcdefghijklmnopqrstuvwxyz
1
1 27

出力例 2

Yes

入力例 3

yzyyyzyzyyyz
8
1 6
7 12
1 12
6 11
1 1
1 3
4 9
3 8

出力例 3

Yes
Yes
Yes
Yes
No
No
No
No

Score : 1300 points

Problem Statement

You are developing a robot that processes strings. When the robot is given a string t consisting of lowercase English letters, it processes the string by following the procedure below:

Let i be the smallest index such that t_i = t_{i + 1}. If such an index does not exist, terminate the procedure.
If t_i is z, remove t_i and t_{i + 1} from t. Otherwise, let c be the next letter of t_i in the English alphabet, and replace t_i and t_{i + 1} together with c, reducing the length of t by 1.
Go back to step 1.

For example, when the robot is given the string axxxxza, it will be processed as follows: axxxxza → ayxxza → ayyza → azza → aa → b.

You are given a string s consisting of lowercase English letters. Answer Q queries. The i-th query is as follows:

Assume that the robot is given a substring of s that runs from the l_i-th character and up to the r_i-th character (inclusive). Will the string be empty after processing?

Constraints

1 ≤ |s| ≤ 5 × 10^5
s consists of lowercase English letters.
1 ≤ Q ≤ 10^5
1 ≤ l_i ≤ r_i ≤ |s|

Input

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

s
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query: Yes or No.

Sample Input 1

axxxxza
2
1 7
2 6

Sample Output 1

No
Yes

Regarding the first query, the string will be processed as follows: axxxxza → ayxxza → ayyza → azza → aa → b.
Regarding the second query, the string will be processed as follows: xxxxz → yxxz → yyz → zz → .

Sample Input 2

aabcdefghijklmnopqrstuvwxyz
1
1 27

Sample Output 2

Yes

Sample Input 3

yzyyyzyzyyyz
8
1 6
7 12
1 12
6 11
1 1
1 3
4 9
3 8

Sample Output 3

Yes
Yes
Yes
Yes
No
No
No
No

D - Oriented Tree

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

配点 : 1800 点

問題文

N 頂点の木 T があります。頂点には 1 から N までの番号が振られています。各 1 ≤ i ≤ N - 1 について、i 番目の辺は頂点 a_i と頂点 b_i を繋いでいます。

すぬけ君は、T のすべての辺をそれぞれ好きな向きに向き付け、有向グラフ T' を作ろうとしています。 (T' は 2^{N - 1} 通りありえます。)

T' をひとつ固定したとき、各 1 ≤ s,\ t ≤ N について d(s,\ t) を次のように定義します。

d(s,\ t) = (頂点 s から頂点 t までのパスに沿って T' 上を移動するとき、辺の向きと逆向きに通るような辺の本数)

特に、各 1 ≤ s ≤ N について d(s,\ s) = 0 です。また、一般に d(s,\ t) ≠ d(t,\ s) であることに注意してください。

さらに、D を次のように定義します。

すぬけ君は、D が最小値をとるように T' を作ろうとしています。 D が最小値をとるような T' は何通りありうるでしょうか？ 10^9 + 7 で割った余りを求めてください。

制約

2 ≤ N ≤ 1000
1 ≤ a_i,\ b_i ≤ N
入力のグラフは木である。

入力

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

N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}

出力

D が最小値をとるような T' は何通りありうるか？ 10^9 + 7 で割った余りを出力せよ。

入力例 1

出力例 1

D の最小値は 1 です。 D が最小値をとるような T' は、次図の 2 通りです。

入力例 2

出力例 2

D の最小値は 2 です。 D が最小値をとるような T' は、次図の 6 通りです。

入力例 3

出力例 3

入力例 4

出力例 4

Score : 1800 points

Problem Statement

There is a tree T with N vertices, numbered 1 through N. For each 1 ≤ i ≤ N - 1, the i-th edge connects vertices a_i and b_i.

Snuke is constructing a directed graph T' by arbitrarily assigning direction to each edge in T. (There are 2^{N - 1} different ways to construct T'.)

For a fixed T', we will define d(s,\ t) for each 1 ≤ s,\ t ≤ N, as follows:

d(s,\ t) = (The number of edges that must be traversed against the assigned direction when traveling from vertex s to vertex t)

In particular, d(s,\ s) = 0 for each 1 ≤ s ≤ N. Also note that, in general, d(s,\ t) ≠ d(t,\ s).

We will further define D as the following:

Snuke is constructing T' so that D will be the minimum possible value. How many different ways are there to construct T' so that D will be the minimum possible value, modulo 10^9 + 7?

Constraints

2 ≤ N ≤ 1000
1 ≤ a_i,\ b_i ≤ N
The given graph is a tree.

Input

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

N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}

Output

Print the number of the different ways to construct T' so that D will be the minimum possible value, modulo 10^9 + 7.

Sample Input 1

Sample Output 1

The minimum possible value for D is 1. There are two ways to construct T' to achieve this value, as shown in the following figure:

Sample Input 2

Sample Output 2

The minimum possible value for D is 2. There are six ways to construct T' to achieve this value, as shown in the following figure:

Sample Input 3

Sample Output 3

Sample Input 4