Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
ナオヒロ君はモンスターを飼っています。モンスターの現在の体力は H です。
また、ナオヒロ君は N 種類の傷薬を持っています。傷薬は効き目の弱い順に 1 から N までの番号がついています。
傷薬 n をモンスターに与えると、モンスターの体力が P_n 増加します。ここで、P_1 \lt P_2 \lt \dots \lt P_N が成り立ちます。
ナオヒロ君は傷薬を 1 つモンスターに与えることで、モンスターの体力を 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 つ与えたときのモンスターの体力の変化は以下の通りです。
- 傷薬 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
Score : 100 points
Problem Statement
Naohiro has a monster. The monster's current health is H.
He also has N kinds of potions, numbered from 1 to N in ascending order of effectiveness.
If you give the monster potion n, its health will increase by P_n. Here, P_1 \lt P_2 \lt \dots \lt P_N.
He wants to increase the monster's health to X or above by giving it one of the potions.
Print the number of the least effective potion that can achieve the purpose. (The constraints guarantee that such a potion exists.)
Constraints
- 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
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H X P_1 P_2 \dots P_N
Output
Print the number of the least effective potion that can achieve the purpose.
Sample Input 1
3 100 200 50 200 999
Sample Output 1
2
Below is the change in the monster's health when one of the potions is given to the monster.
- If potion 1 is given, the monster's health becomes 100 + 50 = 150.
- If potion 2 is given, the monster's health becomes 100 + 200 = 300.
- If potion 3 is given, the monster's health becomes 100 + 999 = 1099.
The potions that increase the monster's health to at least X = 200 are potions 2 and 3. The answer is the least effective of them, which is potion 2.
Sample Input 2
2 10 21 10 999
Sample Output 2
2
Sample Input 3
10 500 999 38 420 490 585 613 614 760 926 945 999
Sample Output 3
4