Al dente

Time Limit : 2 sec, Memory Limit : 65536 KB

A - アルデンテ

問題文

わたしは近所のスーパーで初めてスパゲッティというものを購入した.パッケージの情報によると,このスパゲッティは T 秒茹でると最も理想的な状態に茹で上がるらしい.

ところでわたしは電気が嫌いな人間であり,家にはテレビやパソコンはおろか,時計さえ無い. そのためスパゲッティを茹でようにも,時間を測ることができない. 電池式の時計は嫌なので,わたしは代わりに砂時計を買おうと考え,スーパーの砂時計売り場へと向かった. 売り場には N 個の砂時計があった.i 番目の砂時計はちょうど xi 秒だけ測ることができるようであった. いろいろあって悩ましいが,スパゲッティのために砂時計を何個も買うのは馬鹿らしいのでこの中からちょうど 1 個だけ買おうと思う.

しかし皆さんご存知の通り,砂時計というのは一度測り始めると,それから測り終えるまでは途中の時刻というのはまったく分からない. そのため,もし私が i 番目の砂時計を買って使ったとすると,時計を連続して使うことで xi 秒,2xi 秒,3xi 秒,... という時間を測ることができるが,逆にそれ以外の時間は測ることができない.

理想的な茹で上がりに必要な時間は T 秒らしいが,ここでは妥協して E (< T) 秒以内の誤差を許そう. すなわち,どれか 1 つの砂時計を用いて,T-E 秒,T-E+1 秒,T-E+2 秒,...T+E-2 秒,T+E-1 秒,T+E 秒のうちのどれかの時間を計測したい. 私は何番目の砂時計を購入して使えばよいだろうか?

入力形式

入力は以下の形式で与えられる.

N T E
x1 ... xN

N は砂時計の個数である.T はスパゲッティを理想的に茹で上げるのに必要な時間(秒),E は茹で上げに許容する誤差の時間(秒)である. xii 番目の砂時計が 1 回で測ることできるの時間(秒)である.

出力形式

何番目の砂時計を使えばよいか出力せよ.そのような砂時計が複数個ある場合,それらの中からどれか 1 つを出力せよ. どの砂時計を使っても時間が測れない場合は -1 を出力せよ.

制約

  • 1 ≤ N ≤ 100
  • 1 ≤ T ≤ 1,440
  • 0 ≤ E < T
  • 1 ≤ xi ≤ 10^4
  • 入力値はすべて整数である.

入出力例

入力例 1

2 10 2
3 4

出力例 1

2

8秒,9秒,10秒,11秒,12秒 のうちのいずれかの時間を計測できればよい. 1 番目の砂時計で測ることのできる時間は 3秒,6秒,9秒,12秒,... であり, 2 番目の砂時計で測ることのできる時間は 4秒,8秒,12秒,16秒,... であるので,どちらの砂時計を用いても目的の時間を計測できる. 出力例 1 では 2 を答えとしているが,1 を答えにしても正解である.

入力例 2

3 10 5
16 17 18

出力例 2

-1

どの砂時計を使っても目的の時間は計測できない.


Writer: 花田裕一朗
Tester: 小浜翔太郎

Source: Kyoto University Programming Contest 2012 , Kyoto, Japan, 2012-07-01
http://www.kupc.jp/
http://kupc2012.contest.atcoder.jp/