A - AtCoDeer and Paint Cans

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

シカのAtCoDeerくんはペンキをこれまでに3つ買いました。おととい買ったペンキの色は a , 昨日買ったペンキの色は b , 今日買ったペンキの色は c です。各ペンキの色は1以上100以下の整数で表されます。 AtCoDeerくんはわすれんぼうなため、同じ色のペンキを買ってしまっていることがあります。AtCoDeerくんが買ったペンキの色の種類の個数を教えてあげてください。

• 1≦a,b,c≦100

### 入力

a b c


### 出力

AtCoDeerくんが買ったペンキの色の種類の個数を出力せよ。

### 入力例 1

3 1 4


### 出力例 1

3


1,3,43 種類です。

### 入力例 2

3 3 33


### 出力例 2

2


3,332 種類です。

Score : 100 points

### Problem Statement

AtCoDeer the deer recently bought three paint cans. The color of the one he bought two days ago is a, the color of the one he bought yesterday is b, and the color of the one he bought today is c. Here, the color of each paint can is represented by an integer between 1 and 100, inclusive.

Since he is forgetful, he might have bought more than one paint can in the same color. Count the number of different kinds of colors of these paint cans and tell him.

• 1≦a,b,c≦100

### Input

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

a b c


### Output

Print the number of different kinds of colors of the paint cans.

### Sample Input 1

3 1 4


### Sample Output 1

3


Three different colors: 1, 3, and 4.

### Sample Input 2

3 3 33


### Sample Output 2

2


Two different colors: 3 and 33.

B - Painting Balls with AtCoDeer

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

シカのAtCoDeerくんは一列に並んだ N 個のボールをそれぞれ K 色のペンキの色のうちのどれかで塗ろうとしています。見栄えが悪くならないように、隣り合ったボールは別の色で塗ることにします。ボールの塗り方としてあり得るものの個数を求めてください。

### 制約

• 1≦N≦1000
• 2≦K≦1000
• 答えは 2^{31}-1 以下

### 入力

N K


### 出力

ボールの塗り方としてあり得るものの個数を出力せよ。

### 入力例 1

2 2


### 出力例 1

2


### 入力例 2

1 10


### 出力例 2

10


ボールは一つしか無いため,10色のうちどれを使っても良いので答えは10通りです。

### 入力例 3

10 8


### 出力例 3

322828856


Score : 200 points

### Problem Statement

There are N balls placed in a row. AtCoDeer the deer is painting each of these in one of the K colors of his paint cans. For aesthetic reasons, any two adjacent balls must be painted in different colors.

Find the number of the possible ways to paint the balls.

### Constraints

• 1≦N≦1000
• 2≦K≦1000
• The correct answer is at most 2^{31}-1.

### Input

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

N K


### Output

Print the number of the possible ways to paint the balls.

### Sample Input 1

2 2


### Sample Output 1

2


We will denote the colors by 0 and 1. There are two possible ways: we can either paint the left ball in color 0 and the right ball in color 1, or paint the left in color 1 and the right in color 0.

### Sample Input 2

1 10


### Sample Output 2

10


Since there is only one ball, we can use any of the ten colors to paint it. Thus, the answer is ten.

C - AtCoDeer and Election Report

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

シカの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_iA_i は互いに素 (1≦i≦N)
• 答えが 10^{18} 以下になることは保証されている

### 入力

N
T_1 A_1
T_2 A_2
:
T_N A_N


### 出力

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

### 入力例 1

3
2 3
1 1
3 2


### 出力例 1

10


### 入力例 2

4
1 1
1 1
1 5
1 100


### 出力例 2

101


### 入力例 3

5
3 10
48 17
31 199
231 23
3 2


### 出力例 3

6930


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

3
2 3
1 1
3 2


### Sample Output 1

10


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

4
1 1
1 1
1 5
1 100


### Sample Output 2

101


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

5
3 10
48 17
31 199
231 23
3 2


### Sample Output 3

6930

D - AtCoDeer and Rock-Paper

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

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

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

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

### 制約

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

### 入力

s


### 出力

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

### 入力例 1

gpg


### 出力例 1

0


### 入力例 2

ggppgggpgg


### 出力例 2

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:

s


### Output

Print the AtCoDeer's maximum possible score.

### Sample Input 1

gpg


### Sample Output 1

0


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

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.