2312. 巨龙阿奇的宝箱密码挑战
1000ms
256MB
简单
二分算法
题目描述
巨龙阿奇的黄金宝箱上挂着一把高级的魔法密码锁。密码是一个在 $1$ 到 $10$ 亿之间的正整数 $n$。
挑战者尼格获准使用一台“二分扫描仪”来破解密码。这台扫描仪的工作原理是：每次设定一个搜索区间 $[L, R]$（初始为 $[1, 10^9]$），扫描仪会计算并尝试中间值 $mid = \lfloor (L + R) / 2 \rfloor$：
1. 如果 $mid$ 刚好等于密码 $n$，宝箱开启，挑战成功！
2. 如果 $mid > n$，说明密码在左半边，扫描仪会将右边界更新为 $mid - 1$；
3. 如果 $mid < n$，说明密码在右半边，扫描仪会将左边界更新为 $mid + 1$。
由于扫描仪的能量晶石非常有限，**最多只能支持 20 次扫描尝试**。如果在 20 次及以内（包含 20 次）成功开启宝箱，尼格就能获得“巨龙奖章”（输出 `YES`）；如果超过 20 次还没猜中，或者密码根本不在合理范围内导致无法定位，晶石能量耗尽，挑战失败（输出 `NO`）。
请你编写一个程序，判断对于给定的密码 $n$，尼格是否能获得巨龙奖章。
输入格式
一行，包含一个正整数 $n$ ($1 \le n \le 2 \times 10^9$)，表示宝箱的秘密密码。
输出格式
一行，一个单词。能得到奖章输出 `YES`，否则输出 `NO`。
样例 1
输入 (Input)
500000000
输出 (Output)
YES
样例 2
输入 (Input)
1100000000
输出 (Output)
NO
样例说明
- **样例 1 解释**：
初始区间为 $[1, 10^9]$。第一次扫描计算 $mid = (1 + 10^9) / 2 = 500000000$。由于第一个 $mid$ 刚好等于密码，仅用 1 次扫描就成功开启宝箱，在 20 次限制内，输出 `YES`。
- **样例 2 解释**：
由于密码 $1100000000$ 超出了密码锁设定的合理范围 $[1, 10^9]$，扫描仪在有限次内无法匹配，且最终二分搜索区间会收缩为空，步数超过 20 次，因此输出 `NO`。
- 密码 $n$ 满足 $1 \le n \le 2 \times 10^9$。
- **算法与数据类型提示**：
在二分过程中，`low + high` 可能会接近 $2 \times 10^9$ 甚至更大。为了避免整型溢出，建议在 C++ 中使用 **`long long`** 类型来定义 `low`、`high` 和 `mid`。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功