M-SOLUTIONS Programming Contest

A - Sum of Interior Angles

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

3 以上の整数 N が与えられます。正 N 角形の内角の和を求めてください。

ただし、度数法を用いて、単位は出力しないでください。

制約

3 \leq N \leq 100

入力

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

出力

正 N 角形の内角の和を表す整数を出力せよ。

入力例 1

出力例 1

正三角形の内角の和は 180 度です。

入力例 2

出力例 2

Score : 100 points

Problem Statement

Given an integer N not less than 3, find the sum of the interior angles of a regular polygon with N sides.

Print the answer in degrees, but do not print units.

Constraints

3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:

Output

Print an integer representing the sum of the interior angles of a regular polygon with N sides.

Sample Input 1

Sample Output 1

The sum of the interior angles of a regular triangle is 180 degrees.

Sample Input 2

Sample Output 2

B - Sumo

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

高橋君は相撲の大会に参加しています。大会は 15 日間行われ、高橋君は 1 日 1 番の取組を行います。また、高橋君は 8 番以上勝つと次の大会にも参加できます。

k 日目までの取組が終了しました。高橋君の取組の結果が o, x からなる長さ k の文字列 S で与えられます。 S の i 文字目が o ならば高橋君が i 日目の取組で勝ったことを、 x ならば負けたことをそれぞれ表します。

高橋君が次の大会にも参加できる可能性があるならば YES を、そのような可能性がないならば NO を出力してください。

制約

1 \leq k \leq 15
S は o, x からなる長さ k の文字列である

入力

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

出力

高橋君が次の大会にも参加できる可能性があるならば YES と出力せよ。そのような可能性がないならば NO と出力せよ。

入力例 1

oxoxoxoxoxoxox

出力例 1

YES

高橋君は 14 試合目までで 7 勝 7 敗なので、最後の取組に勝つと 8 番勝つことができます。

入力例 2

xxxxxxxx

出力例 2

NO

Score : 200 points

Problem Statement

Takahashi is competing in a sumo tournament. The tournament lasts for 15 days, during which he performs in one match per day. If he wins 8 or more matches, he can also participate in the next tournament.

The matches for the first k days have finished. You are given the results of Takahashi's matches as a string S consisting of o and x. If the i-th character in S is o, it means that Takahashi won the match on the i-th day; if that character is x, it means that Takahashi lost the match on the i-th day.

Print YES if there is a possibility that Takahashi can participate in the next tournament, and print NO if there is no such possibility.

Constraints

1 \leq k \leq 15
S is a string of length k consisting of o and x.

Input

Input is given from Standard Input in the following format:

Output

Print YES if there is a possibility that Takahashi can participate in the next tournament, and print NO otherwise.

Sample Input 1

oxoxoxoxoxoxox

Sample Output 1

YES

Takahashi has 7 wins and 7 losses before the last match. If he wins that match, he will have 8 wins.

Sample Input 2

xxxxxxxx

Sample Output 2

NO

C - Best-of-(2n-1)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

高橋君と青木君がゲームをします。どちらかが合計で N 回勝つまでゲームを繰り返し行います。

1 回ゲームを行ったとき、高橋君が勝つ確率は A %、青木君が勝つ確率は B %、どちらも勝たず引き分けとなる確率は C %です。ゲームが行われる回数の期待値を求めて、以下のように出力してください。

求める期待値は互いに素な整数 P, Q を用いて P/Q と表せます。 R \times Q \equiv P\pmod {10^9+7} となる 0 以上 10^9+6 以下の整数 R を出力してください。 (この問題の制約下で、このような R は必ず一意に存在します。)

制約

1 \leq N \leq 100000
0 \leq A,B,C \leq 100
1 \leq A+B
A+B+C=100
入力はすべて整数である

入力

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

N A B C

出力

ゲームが行われる回数の期待値を問題文で指定した方法にしたがって出力せよ。

入力例 1

1 25 25 50

出力例 1

N=1 なのでゲームはどちらかが勝つまで繰り返されます。期待値は 2 となります。

入力例 2

4 50 50 0

出力例 2

312500008

C=0 となることがあります。

入力例 3

1 100 0 0

出力例 3

B=0 となることもあります。

入力例 4

100000 31 41 28

出力例 4

104136146

Score : 500 points

Problem Statement

Takahashi and Aoki will play a game. They will repeatedly play it until one of them have N wins in total.

When they play the game once, Takahashi wins with probability A %, Aoki wins with probability B %, and the game ends in a draw (that is, nobody wins) with probability C %. Find the expected number of games that will be played, and print it as follows.

We can represent the expected value as P/Q with coprime integers P and Q. Print the integer R between 0 and 10^9+6 (inclusive) such that R \times Q \equiv P\pmod {10^9+7}. (Such an integer R always uniquely exists under the constraints of this problem.)

Constraints

1 \leq N \leq 100000
0 \leq A,B,C \leq 100
1 \leq A+B
A+B+C=100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A B C

Output

Print the expected number of games that will be played, in the manner specified in the statement.

Sample Input 1

1 25 25 50

Sample Output 1

Since N=1, they will repeat the game until one of them wins. The expected number of games played is 2.

Sample Input 2

4 50 50 0

Sample Output 2

312500008

C may be 0.

Sample Input 3

1 100 0 0

Sample Output 3

B may also be 0.

Sample Input 4

100000 31 41 28

Sample Output 4

104136146

D - Maximum Sum of Minimum

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 個の頂点 1,2,\ldots,N からなる木 T と正の整数 c_1,c_2,\ldots,c_N が与えられます。 i(1 \leq i \leq N-1) 番目の辺は頂点 a_i と頂点 b_i をつなぐ辺です。

T の各頂点に正の整数を書き込んだとき、以下のようにしてスコアを計算します。

各辺に、2 つの端点に書き込まれた整数のうち小さい方を書き込む。
各辺に書き込まれた整数の総和をスコアとする。

T の各頂点に c_1,c_2,\ldots,c_N を 1 つずつ書き込んだときのスコアの最大値を求め、それを達成する正の整数の書き込み方を 1 つ構成してください。

c_1,c_2,\ldots,c_N に複数回現れる整数があるときは、その整数はその回数だけ使わなければならないことに注意してください。

制約

1 \leq N \leq 10000
1 \leq a_i,b_i \leq N
1 \leq c_i \leq 10^5
与えられるグラフは木である

入力

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

N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 \ldots c_N

出力

次の形式で出力せよ。

M
d_1 \ldots d_N

M はスコアの最大値を表す。 d_i は頂点 i に書き込むべき整数を表す。 d_1,d_2,\ldots,d_N は c_1,c_2,\ldots,c_N の並べ替えでなければならない。

最大のスコアを達成する方法が複数個あるときは、そのうちのどれを出力してもよい。

入力例 1

出力例 1

10
1 2 3 4 5

頂点 1,2,3,4,5 にそれぞれ 1,2,3,4,5 を書き込むと、 4 つの辺にはそれぞれ 1,2,3,4 が書き込まれるので、スコアは 10 になります。

これが最大のスコアです。

入力例 2

5
1 2
1 3
1 4
1 5
3141 59 26 53 59

出力例 2

197
59 26 3141 59 53

c_1,c_2,\ldots,c_N は互いに異なるとは限りません。

Score : 500 points

Problem Statement

You are given a tree with N vertices 1,2,\ldots,N, and positive integers c_1,c_2,\ldots,c_N. The i-th edge in the tree (1 \leq i \leq N-1) connects Vertex a_i and Vertex b_i.

We will write a positive integer on each vertex in T and calculate our score as follows:

On each edge, write the smaller of the integers written on the two endpoints.
Let our score be the sum of the integers written on all the edges.

Find the maximum possible score when we write each of c_1,c_2,\ldots,c_N on one vertex in T, and show one way to achieve it. If an integer occurs multiple times in c_1,c_2,\ldots,c_N, we must use it that number of times.

Constraints

1 \leq N \leq 10000
1 \leq a_i,b_i \leq N
1 \leq c_i \leq 10^5
The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 \ldots c_N

Output

Use the following format:

M
d_1 \ldots d_N

where M is the maximum possible score, and d_i is the integer to write on Vertex i. d_1,d_2,\ldots,d_N must be a permutation of c_1,c_2,\ldots,c_N. If there are multiple ways to achieve the maximum score, any of them will be accepted.

Sample Input 1

Sample Output 1

10
1 2 3 4 5

If we write 1,2,3,4,5 on Vertex 1,2,3,4,5, respectively, the integers written on the four edges will be 1,2,3,4, for the score of 10. This is the maximum possible score.

Sample Input 2

5
1 2
1 3
1 4
1 5
3141 59 26 53 59

Sample Output 2

197
59 26 3141 59 53

c_1,c_2,\ldots,c_N may not be pairwise distinct.

E - Product of Arithmetic Progression

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

以下のような、n 項からなる等差数列を考えます。

x, x + d, x + 2d, \ldots, x + (n-1)d

この数列のすべての項の積はいくつでしょうか？その積を 1,000,003 で割った余りを計算してください。

この形式の問いが Q 個与えられます。 i 個目の問いでは、x = x_i, d = d_i, n = n_i の場合の答えを計算してください。

制約

1 \leq Q \leq 10^5
0 \leq x_i, d_i \leq 1,000,002
1 \leq n_i \leq 10^9
入力中の値はすべて整数である。

入力

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

Q
x_1 d_1 n_1
:
x_Q d_Q n_Q

出力

Q 行出力せよ。

i 行目に、i 個目の問いに対する答えを出力せよ。

入力例 1

2
7 2 4
12345 67890 2019

出力例 1

9009
916936

最初のクエリに対し、答えは 7 \times 9 \times 11 \times 13 = 9009 です。積を 1,000,003 で割った余りを求めることをお忘れなく。

Score : 600 points

Problem Statement

Consider the following arithmetic progression with n terms:

x, x + d, x + 2d, \ldots, x + (n-1)d

What is the product of all terms in this sequence? Compute the answer modulo 1\ 000\ 003.

You are given Q queries of this form. In the i-th query, compute the answer in case x = x_i, d = d_i, n = n_i.

Constraints

1 \leq Q \leq 10^5
0 \leq x_i, d_i \leq 1\ 000\ 002
1 \leq n_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Q
x_1 d_1 n_1
:
x_Q d_Q n_Q

Output

Print Q lines.

In the i-th line, print the answer for the i-th query.

Sample Input 1

2
7 2 4
12345 67890 2019

Sample Output 1

9009
916936

For the first query, the answer is 7 \times 9 \times 11 \times 13 = 9009. Don't forget to compute the answer modulo 1\ 000\ 003.

F - Random Tournament

Time Limit: 2.5 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N 人の参加するじゃんけん大会を行います。参加者は人 1, 人 2, \ldots, 人 N と呼ばれます。どの 2 人についてもその 2 人がじゃんけんをしたときにどちらが勝利するかが事前に決まっています。この情報は正の整数 A_{i,j} ( 1 \leq j < i \leq N ) によって表され、

A_{i,j} = 0 のとき、人 i は人 j に負けること
A_{i,j} = 1 のとき、人 i は人 j に勝つこと

をそれぞれ表します。

大会は次のようにして行われます。

N 人の参加者を人 1, 人 2, \ldots, 人 N の順に横一列に並べる。
列で連続している 2 人をランダムに選んで、その 2 人で試合を行い、負けた人を列から外す。これを N-1 回繰り返し、最後に残った 1 人を優勝者とする。

優勝する可能性のある人の人数を求めてください。

制約

1 \leq N \leq 2000
A_{i,j} は 0 または 1

入力

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

N
A_{2,1}
A_{3,1}A_{3,2}
:
A_{N,1}\ldotsA_{N,N-1}

出力

優勝する可能性のある人の人数を出力せよ。

入力例 1

3
0
10

出力例 1

人 1 は人 2 に勝ち、人 2 は人 3 に勝ち、人 3 は人 1 に勝ちます。最初に人 1 と人 2 が試合をすると人 3 が優勝し、最初に人 2 と人 3 が試合をすると人 1 が優勝します。

入力例 2

出力例 2

Score : 1000 points

Problem Statement

We will host a rock-paper-scissors tournament with N people. The participants are called Person 1, Person 2, \ldots, Person N. For any two participants, the result of the match between them is determined in advance. This information is represented by positive integers A_{i,j} ( 1 \leq j < i \leq N ) as follows:

If A_{i,j} = 0, Person j defeats Person i.
If A_{i,j} = 1, Person i defeats Person j.

The tournament proceeds as follows:

We will arrange the N participants in a row, in the order Person 1, Person 2, \ldots, Person N from left to right.
We will randomly choose two consecutive persons in the row. They will play a match against each other, and we will remove the loser from the row. We will repeat this process N-1 times, and the last person remaining will be declared the champion.

Find the number of persons with the possibility of becoming the champion.

Constraints

1 \leq N \leq 2000
A_{i,j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

N
A_{2,1}
A_{3,1}A_{3,2}
:
A_{N,1}\ldotsA_{N,N-1}

Output

Print the number of persons with the possibility of becoming the champion.

Sample Input 1

3
0
10

Sample Output 1

Person 1 defeats Person 2, Person 2 defeats Person 3 and Person 3 defeats Person 1. If Person 1 and Person 2 play the first match, Person 3 will become the champion. If Person 2 and Person 3 play the first match, Person 1 will become the champion.

Sample Input 2