実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 100 点
問題文
シカの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,4 の 3 種類です。
入力例 2
3 3 33
出力例 2
2
色 3,33 の 2 種類です。
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.
Constraints
- 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.
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 200 点
問題文
シカのAtCoDeerくんは一列に並んだ N 個のボールをそれぞれ K 色のペンキの色のうちのどれかで塗ろうとしています。見栄えが悪くならないように、隣り合ったボールは別の色で塗ることにします。ボールの塗り方としてあり得るものの個数を求めてください。
制約
- 1≦N≦1000
- 2≦K≦1000
- 答えは 2^{31}-1 以下
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
ボールの塗り方としてあり得るものの個数を出力せよ。
入力例 1
2 2
出力例 1
2
色を0,1で表すと、左のボールを0で塗り、右のボールを1で塗る という方法と、 左のボールを1で塗り、右のボールを0で塗る という方法の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.
実行時間制限: 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
3 2 3 1 1 3 2
出力例 1
10
二人の得票数が 2,3 -> 3,3 -> 6,4 と動くと投票数は 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
実行時間制限: 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 で表される手は、条件(※)を満たしている
入力
入力は以下の形式で標準入力から与えられる。
s
出力
AtCoDeerくんの得点の最大値を出力せよ。
入力例 1
gpg
出力例 1
0
常に相手とあいこになるように手を出すことで、0点を取ることができて、これが最大値です。
入力例 2
ggppgggpgg
出力例 2
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
gorp. - 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.