Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
高橋君はレベル N の赤い宝石を 1 個持っています。(他に宝石は持っていません。)
高橋君は次の操作を好きなだけ行うことができます。
- レベル n の赤い宝石 (n は 2 以上) を「レベル n-1 の赤い宝石 1 個と、レベル n の青い宝石 X 個」に変換する。
- レベル n の青い宝石 (n は 2 以上) を「レベル n-1 の赤い宝石 1 個と、レベル n-1 の青い宝石 Y 個」に変換する。
高橋君はレベル 1 の青い宝石ができるだけたくさんほしいです。操作によって高橋君はレベル 1 の青い宝石を最大何個入手できますか?
制約
- 1 \leq N \leq 10
- 1 \leq X \leq 5
- 1 \leq Y \leq 5
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X Y
出力
答えを出力せよ。
入力例 1
2 3 4
出力例 1
12
次のような変換を行うことで、高橋君はレベル 1 の青い宝石を 12 個手に入れることができます。
- まず、レベル 2 の赤い宝石 1 個を、レベル 1 の赤い宝石 1 個とレベル 2 の青い宝石 3 個に変換します。
- 操作後の高橋君は、レベル 1 の赤い宝石 1 個とレベル 2 の青い宝石 3 個を持っています。
- 次に、レベル 2 の青い宝石 1 個を、レベル 1 の赤い宝石 1 個とレベル 1 の青い宝石 4 個に変換します。この変換を 3 回繰り返します。
- 操作後の高橋君は、レベル 1 の赤い宝石 4 個とレベル 1 の青い宝石 12 個を持っています。
- これ以上変換を行うことはできません。
12 個より多くレベル 1 の青い宝石を手に入れることはできないので、答えは 12 になります。
入力例 2
1 5 5
出力例 2
0
高橋君がレベル 1 の青い宝石を 1 個も手に入れられない場合もあります。
入力例 3
10 5 5
出力例 3
3942349900
答えが 32 bit 整数に収まらない場合があることに注意してください。
Score : 300 points
Problem Statement
Takahashi has a red jewel of level N. (He has no other jewels.)
Takahashi can do the following operations any number of times.
- Convert a red jewel of level n (n is at least 2) into "a red jewel of level (n-1) and X blue jewels of level n".
- Convert a blue jewel of level n (n is at least 2) into "a red jewel of level (n-1) and Y blue jewels of level (n-1)".
Takahashi wants as many blue jewels of level 1 as possible. At most, how many blue jewels of level 1 can he obtain by the operations?
Constraints
- 1 \leq N \leq 10
- 1 \leq X \leq 5
- 1 \leq Y \leq 5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X Y
Output
Print the answer.
Sample Input 1
2 3 4
Sample Output 1
12
Takahashi can obtain 12 blue jewels of level 1 by the following conversions.
- First, he converts a red jewel of level 2 into a red jewel of level 1 and 3 blue jewels of level 2.
- After this operation, Takahashi has 1 red jewel of level 1 and 3 blue jewels of level 2.
- Next, he repeats the following conversion 3 times: converting a blue jewel of level 2 into a red jewel of level 1 and 4 blue jewels of level 1.
- After these operations, Takahashi has 4 red jewels of level 1 and 12 blue jewels of level 1.
- He cannot perform a conversion anymore.
He cannot obtain more than 12 blue jewels of level 1, so the answer is 12.
Sample Input 2
1 5 5
Sample Output 2
0
Takahashi may not be able to obtain a blue jewel of level 1.
Sample Input 3
10 5 5
Sample Output 3
3942349900
Note that the answer may not fit into a 32-bit integer type.