← 返回题目列表

AtCoder · awc0021_e

E. 田间浇水计划

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥将浇灌他的田地 N 天。每天,他都会选择并执行两种浇水方法中的一种。

方法A 是一种一次性喷洒大量水的方法。当选择这个方法的那一天,基本上会产生增长量 a,但由于浇水太多,土壤变得渍水,在上面获得的生长量 第二天 减半(此后的日子没有影响)。

方法B 是一种小心地撒少量水的方法。当选择这个方法的那一天,基本上会产生增长量 b。由于对土壤没有任何负担,因此对第二天不会产生负面影响。

具体来说,每天的增长量由以下规则确定:

  • 如果前一天使用了方法B,或者是第一天(不存在前一天),则不会发生减半。如果选择方法A,则增长量为 a;如果选择方法B,则增长量为 b.
  • 如果前一天使用方法 A,当日成长量减半。如果选择方法A,则增长量为 \lfloor a / 2 \rfloor;如果选择方法B,则增长量为 \lfloor b / 2 \rfloor。在这里, \lfloor x \rfloor 表示不超过的最大整数 x.

减半始终应用于基值 a or b。前一天的增长量是否减半并不重要;该决定仅基于“前一天是否使用了方法 A”。例如,如果连续三天选择方法A,则增长量为 a 第一天, \lfloor a/2 \rfloor 第二天,以及 \lfloor a/2 \rfloor 第三天。

求浇水方式超过时的最大可能总生长量 N 天是最佳选择的。

约束

  • 1 \leq N \leq 10^{18}
  • 1 \leq a \leq 10^9
  • 1 \leq b \leq 10^9
  • 所有输入值均为整数。

输入

N a b
  • 第一行包含天数 N,方法A的基础生长量 a,以及方法B的基础生长量 b,以空格分隔。

输出

在一行中输出最大可能的总生长量。


示例输入 1

5 10 3

示例输出 1

32

示例输入 2

4 3 5

示例输出 2

20

示例输入 3

100 100 51

示例输出 3

6276

示例输入 4

1000000000000 100000 1

示例输出 4

50000000000050000

示例输入 5

1 1 1

示例输出 5

1