#XMOJ12271. 溢出幻想

溢出幻想

说明

时间限制:1 Sec 内存限制:256 MB 输入文件:fantasy.in 输出文件:fantasy.out

游戏《Fantasy》使用 $N$ 位有符号整数($2$ 的补码)管理数值。

正常规则:把敌人血量降到 $0$ 及以下,即可击杀敌人。

溢出 bug 打法:可以主动回血,利用有符号整数加法溢出,让血量溢出后变成负数,同样判定击杀。

敌人初始血量 $X$;

每次攻击:血量减少 $A$,耗时 $1$ 单位时间;

每次回血:血量增加 $B$,耗时 $1$ 单位时间。

攻击、回血每次操作都消耗 $1$ 单位时间。敌人自身不会改变血量。

求击杀敌人需要的最小时间。

$2$ 的补码说明

对于 $N$ 位有符号整数,取值范围:$-2^{N-1} \le x < 2^{N-1}$。

$$ x = -2^{N-1}\cdot a_{N-1}+\sum_{k=0}^{N-2} 2^k a_k $$

$a_i\in\{0,1\}$。

加法规则:普通二进制加法,超出最高位的进位直接丢弃。

输入格式

第一行一个整数 $N$。

第二行一个整数 $X$。

第三行一个整数 $A$。

第四行一个整数 $B$。

输出格式

输出击杀敌人的最短时间。

样例

样例 1

4
4
3
1

2

样例说明:

44 位有符号整数。连续攻击 22 次即可击杀。

第 $1$ 次攻击:$4-3=1$

第 $2$ 次攻击:$1-3=-2$,小于 $0$,击杀。

样例 2

4
6
2
1

2

样例说明:

连续回血 22 次触发溢出。

$(6+1=7)$,$(7+1=8)$。$4$ 位 $2$ 补码下 $8$ 代表 $-8$,判定击杀。

样例 3

26
16777221
20
20

838861

样例说明:

攻击需要 838862838862 次;回血只需要 838861838861 次,选回血方案。

数据范围

对于 20% 的数据,$N \le 8$。

对于 40% 的数据,$N \le 16$。

对于 100% 的数据,$2\le N \le 32$,$1\le X,A,B \lt 2^{N-1}$。