E - Changing Jewels Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

高橋君はレベル N の赤い宝石を 1 個持っています。(他に宝石は持っていません。)
高橋君は次の操作を好きなだけ行うことができます。

  • レベル n の赤い宝石 (n2 以上) を「レベル n-1 の赤い宝石 1 個と、レベル n の青い宝石 X 個」に変換する。
  • レベル n の青い宝石 (n2 以上) を「レベル 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.