AtCoder Regular Contest 062

C - AtCoDeerくんと選挙速報

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

配点 : 300 点

問題文

シカのAtCoDeerくんは選挙速報を見ています。選挙には二人の候補高橋くんと青木くんが出ています。速報では、現在の二人の得票数の比が表示されていますが、得票数そのものは表示されていません。AtCoDeerくんは N 回画面を見て、 i(1≦i≦N) 回目に見たときに表示されている比は T_i:A_i でした。ここで、AtCoDeerくんが選挙速報の画面を1回目に見た段階で既にどちらの候補にも少なくとも一票は入っていたことがわかっています。 N 回目に画面を見たときの投票数(二人の得票数の和)として考えられるもののうち最小となるものを求めてください。ただし、得票数が途中で減ることはありません。

制約

1≦N≦1000
1≦T_i,A_i≦1000 (1≦i≦N)
T_i と A_i は互いに素 (1≦i≦N)
答えが 10^{18} 以下になることは保証されている

入力

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

N
T_1 A_1
T_2 A_2
:
T_N A_N

出力

N 回目に画面を見たときの投票数として考えられる最小値を出力せよ。

入力例 1

出力例 1

二人の得票数が 2,3 -> 3,3 -> 6,4 と動くと投票数は 10 になって、これが最小値です。

入力例 2

出力例 2

一度画面を見てからもう一度画面を見るまでに一票も入ってないことがありえます。

入力例 3

出力例 3

Score : 300 points

Problem Statement

AtCoDeer the deer is seeing a quick report of election results on TV. Two candidates are standing for the election: Takahashi and Aoki. The report shows the ratio of the current numbers of votes the two candidates have obtained, but not the actual numbers of votes. AtCoDeer has checked the report N times, and when he checked it for the i-th (1≦i≦N) time, the ratio was T_i:A_i. It is known that each candidate had at least one vote when he checked the report for the first time.

Find the minimum possible total number of votes obtained by the two candidates when he checked the report for the N-th time. It can be assumed that the number of votes obtained by each candidate never decreases.

Constraints

1≦N≦1000
1≦T_i,A_i≦1000 (1≦i≦N)
T_i and A_i (1≦i≦N) are coprime.
It is guaranteed that the correct answer is at most 10^{18}.

Input

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

N
T_1 A_1
T_2 A_2
:
T_N A_N

Output

Print the minimum possible total number of votes obtained by Takahashi and Aoki when AtCoDeer checked the report for the N-th time.

Sample Input 1

Sample Output 1

When the numbers of votes obtained by the two candidates change as 2,3 → 3,3 → 6,4, the total number of votes at the end is 10, which is the minimum possible number.

Sample Input 2

Sample Output 2

It is possible that neither candidate obtained a vote between the moment when he checked the report, and the moment when he checked it for the next time.

Sample Input 3

Sample Output 3

D - AtCoDeerくんと変なじゃんけん

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

配点 : 300 点

問題文

シカのAtCoDeerくんは友達のTopCoDeerくんとあるゲームをして対戦しています。このゲームは N ターンからなります。各ターンではそれぞれのプレイヤーはじゃんけんのグーかパーを出します。ただし、各プレイヤーは次の条件を満たす必要があります。

(※) 各ターンの後で、(今までにパーを出した回数)≦(今までにグーを出した回数)　を満たす

このゲームでの各プレイヤーの得点は、(勝ったターンの数) - (負けたターンの数) です。 AtCoDeerくんは特殊能力を持っているので、ゲームが始まる前にTopCoDeerくんの出す N ターンの手を全て知ることが出来ました。 AtCoDeerくんの各ターンでの手を決めて、AtCoDeerくんの得点を最大化してください。 TopCoDeerくんの出す手の情報は文字列 s で与えられます。 s の i(1≦i≦N) 文字目が gのときは i ターン目でTopCoDeerくんがグーを出すことを、 pのときはパーを出すことを表します。

制約

1≦N≦10^5
N=|s|
s の各文字はgかp
s で表される手は、条件(※)を満たしている

入力

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

出力

AtCoDeerくんの得点の最大値を出力せよ。

入力例 1

gpg

出力例 1

常に相手とあいこになるように手を出すことで、0点を取ることができて、これが最大値です。

入力例 2

ggppgggpgg

出力例 2

例えばグー,パー,グー,パー,グー,グー,パー,パー,グー,パーと出すことで、 3回勝って1回負けているので得点は2点になり、これが最大値です。

Score : 300 points

Problem Statement

AtCoDeer the deer and his friend TopCoDeer is playing a game. The game consists of N turns. In each turn, each player plays one of the two gestures, Rock and Paper, as in Rock-paper-scissors, under the following condition:

(※) After each turn, (the number of times the player has played Paper)≦(the number of times the player has played Rock).

Each player's score is calculated by (the number of turns where the player wins) - (the number of turns where the player loses), where the outcome of each turn is determined by the rules of Rock-paper-scissors.

(For those who are not familiar with Rock-paper-scissors: If one player plays Rock and the other plays Paper, the latter player will win and the former player will lose. If both players play the same gesture, the round is a tie and neither player will win nor lose.)

With his supernatural power, AtCoDeer was able to foresee the gesture that TopCoDeer will play in each of the N turns, before the game starts. Plan AtCoDeer's gesture in each turn to maximize AtCoDeer's score.

The gesture that TopCoDeer will play in each turn is given by a string s. If the i-th (1≦i≦N) character in s is g, TopCoDeer will play Rock in the i-th turn. Similarly, if the i-th (1≦i≦N) character of s in p, TopCoDeer will play Paper in the i-th turn.

Constraints

1≦N≦10^5
N=|s|
Each character in s is g or p.
The gestures represented by s satisfy the condition (※).

Input

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

Output

Print the AtCoDeer's maximum possible score.

Sample Input 1

gpg

Sample Output 1

Playing the same gesture as the opponent in each turn results in the score of 0, which is the maximum possible score.

Sample Input 2

ggppgggpgg

Sample Output 2

For example, consider playing gestures in the following order: Rock, Paper, Rock, Paper, Rock, Rock, Paper, Paper, Rock, Paper. This strategy earns three victories and suffers one defeat, resulting in the score of 2, which is the maximum possible score.

E - AtCoDeerくんと立方体づくり

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

配点 : 900 点

問題文

シカのAtCoDeerくんは正方形のタイルを N 枚持っています。各正方形の片面には 1～N の数が書いてあって、正方形の各頂点にはそれぞれ色が塗られています。色は 0～999の整数で表され、 i と書かれた正方形に塗られている色は、数の書かれている方向から見て左上、右上、右下、左下の順に、 C_{i,0},C_{i,1},C_{i,2},C_{i,3} で与えられます(図1を参照)。

図1: タイルの色と入力の対応

AtCoDeerくんはこれらのタイルを6枚組み合わせて次のような条件を満たす立方体を作ろうと考えました。

数の書いてある面が外側を向いている
立方体の各頂点に対し、そこに集まる正方形の頂点は3つあるが、それらには全て同じ色が塗られている

AtCoDeerくんのために条件を満たす立方体が何通りあるか求めてください。ただし、正方形には数が書いてあるので、色の構成が同じだとしても使ったタイルが異なったり、使ったタイルの向き(90°回転により4通り考えられる)が異なるものは異なる立方体とみなします。ただし、3次元空間で回転させることで使ったタイルの向きまで完全に一致するものは同じ立方体とみなします。

図2: 4方向のタイルの向き

制約

6≦N≦400
0≦C_{i,j}≦999 (1≦i≦N , 0≦j≦3)

入力

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

N
C_{1,0} C_{1,1} C_{1,2} C_{1,3}
C_{2,0} C_{2,1} C_{2,2} C_{2,3}
:
C_{N,0} C_{N,1} C_{N,2} C_{N,3}

出力

AtCoDeerくんが作れる立方体が何通りあるか出力せよ。

入力例 1

出力例 1

下図のような立方体が作れます。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 900 points

Problem Statement

AtCoDeer the deer has N square tiles. The tiles are numbered 1 through N, and the number given to each tile is written on one side of the tile. Also, each corner of each tile is painted in one of the 1000 colors, which are represented by the integers 0 between 999. The top-left, top-right, bottom-right and bottom-left corner of the tile with the number i are painted in color C_{i,0}, C_{i,1}, C_{i,2} and C_{i,3}, respectively, when seen in the direction of the number written on the tile (See Figure 1).

Figure 1: The correspondence between the colors of a tile and the input

AtCoDeer is constructing a cube using six of these tiles, under the following conditions:

For each tile, the side with the number must face outward.
For each vertex of the cube, the three corners of the tiles that forms it must all be painted in the same color.

Help him by finding the number of the different cubes that can be constructed under the conditions. Since each tile has a number written on it, two cubes are considered different if the set of the used tiles are different, or the tiles are used in different directions, even if the formation of the colors are the same. (Each tile can be used in one of the four directions, obtained by 90° rotations.) Two cubes are considered the same only if rotating one in the three dimensional space can obtain an exact copy of the other, including the directions of the tiles.

Figure 2: The four directions of a tile

Constraints

6≦N≦400
0≦C_{i,j}≦999 (1≦i≦N , 0≦j≦3)

Input

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

N
C_{1,0} C_{1,1} C_{1,2} C_{1,3}
C_{2,0} C_{2,1} C_{2,2} C_{2,3}
:
C_{N,0} C_{N,1} C_{N,2} C_{N,3}

Output

Print the number of the different cubes that can be constructed under the conditions.

Sample Input 1

Sample Output 1

The cube below can be constructed.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

F - AtCoDeerくんとグラフ色塗り

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

配点 : 1300 点

問題文

シカのAtCoDeerくんはある日、 N 頂点 M 辺からなる単純な(すなわち、多重辺と自己ループのない)グラフを拾いました。頂点には1,2,..,Nの番号がついていて互いに区別が可能で、辺は(a_i,b_i) (1≦i≦M)で表されます。 AtCoDeerくんは K 色のペンキを使って各辺を塗ろうとしています。ペンキは大量にあるので同じ色で複数の辺を塗ることが可能です。 AtCoDeerくんの拾ったグラフは特殊な形状をしているため、単純なサイクル(すなわち,サイクルであって同じ頂点を一度しか通らないもの)を選んで、そのサイクル上の辺の色をひとつずつサイクルに沿ってずらすことが出来ます。正確に言うと、サイクル上の辺を順に e_1, e_2,..,e_a とすると、 e_1 に塗られていた色を e_2 に、e_2 に塗られていた色を e_3 に、 ...、 e_{a-1} に塗られていた色を e_a に、e_a に塗られていた色を e_1 に、同時に塗り替えることが出来ます。

図1: 操作の例

塗り方Aと塗り方Bは、この操作を有限回行ってAからBに変形できるときに同じ塗り方だとみなします。グラフの塗り方が何通りあるか求めてください。ただしこの数は非常に大きくなることがあるので、 10^9+7 で割ったあまりを出力してください。

制約

1≦N≦50
1≦M≦100
1≦K≦100
1≦a_i,b_i≦N (1≦i≦M)
グラフには自己ループや多重辺はない。

入力

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

N M K
a_1 b_1
a_2 b_2
:
a_M b_M

出力

塗り方が何通りあるかを 10^9+7 で割ったあまりを出力せよ。

入力例 1

出力例 1

入力例 2

5 2 3
1 2
4 5

出力例 2

入力例 3

出力例 3

569519295

Score : 1300 points

Problem Statement

One day, AtCoDeer the deer found a simple graph (that is, a graph without self-loops and multiple edges) with N vertices and M edges, and brought it home. The vertices are numbered 1 through N and mutually distinguishable, and the edges are represented by (a_i,b_i) (1≦i≦M).

He is painting each edge in the graph in one of the K colors of his paint cans. As he has enough supply of paint, the same color can be used to paint more than one edge.

The graph is made of a special material, and has a strange property. He can choose a simple cycle (that is, a cycle with no repeated vertex), and perform a circular shift of the colors along the chosen cycle. More formally, let e_1, e_2, ..., e_a be the edges along a cycle in order, then he can perform the following simultaneously: paint e_2 in the current color of e_1, paint e_3 in the current color of e_2, ..., paint e_a in the current color of e_{a-1}, and paint e_1 in the current color of e_{a}.

Figure 1: An example of a circular shift

Two ways to paint the edges, A and B, are considered the same if A can be transformed into B by performing a finite number of circular shifts. Find the number of ways to paint the edges. Since this number can be extremely large, print the answer modulo 10^9+7.

Constraints

1≦N≦50
1≦M≦100
1≦K≦100
1≦a_i,b_i≦N (1≦i≦M)
The graph has neither self-loops nor multiple edges.

Input

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

N M K
a_1 b_1
a_2 b_2
:
a_M b_M

Output

Print the number of ways to paint the edges, modulo 10^9+7.

Sample Input 1

Sample Output 1

Sample Input 2

5 2 3
1 2
4 5

Sample Output 2

Sample Input 3

Sample Output 3

569519295