分数: 100 点
问题陈述
直宏有一个怪物。怪物当前的生命值是 H.
他还有 N 药剂种类,编号为 1 to N 按有效性升序排列。
如果你给予怪物药水 n,其生命值将增加 P_n。在这里, P_1 \lt P_2 \lt \dots \lt P_N.
他想将怪物的生命值增加到 X 或以上,给它一种药水。
打印能达到目的的最低有效药水的编号。 (约束条件保证了这样的药剂存在。)
约束
- 2 \leq N \leq 100
- 1 \leq H \lt X \leq 999
- 1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N H X P_1 P_2 \dots P_N
输出
打印能达到目的的最低有效药水的编号。
示例输入 1
3 100 200 50 200 999
示例输出 1
2
下面是给怪物提供一种药水时怪物生命值的变化。
- 如果药水 给予 1 ,怪物的生命值变为 100 + 50 = 150.
- 如果药水 给予 2 ,怪物的生命值变为 100 + 200 = 300.
- 如果药水 给予 3 ,怪物的生命值变为 100 + 999 = 1099.
使怪物的生命值至少增加到的药水 X = 200 是药水 2 和 3。 答案是其中效果最差的,那就是药水 2.
示例输入 2
2 10 21 10 999
示例输出 2
2
示例输入 3
10 500 999 38 420 490 585 613 614 760 926 945 999
示例输出 3
4