ECOO '17 R2 P3 - Lunch Time

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 13.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Since beginning her university studies, Ava has been going to a nearby plaza for lunch. In order to maintain good eating habits throughout her university career, Ava has crafted a perfect dining strategy.

Ava began by eating at each of the N restaurants (numbered 1 through N) at the plaza and rating how much she enjoyed the food. Once she gathered all he ratings, she would only eat at the highest-rated restaurant. (If there is a tie, she eats at the lowest-numbered restaurant.) However, after a week of eating the same food, Ava realized she needs more variety in her diet. To fix this issue, she decided that eating at a restuarant would cause its rating to drop by a fixed amount, M.

Armed with her dining strategy, Ava wonders where she will grab lunch on her last day of university, which is K days away if she eats at exactly one restaurant per day.

Input Specification

The input will contain 10 test cases. Each test case starts with three integers N, M (1 \le N, M \le 10^5), K (1 \le K \le 10^{12}). The next line contains N positive integers R_p (1 \le R_p \le 10^9), where R_p represents the rating of the p^{th} restaurant at the plaza. Restaurants are numbered starting from 1.

For the first four test cases in the file, N \cdot K \le 10^6. For the first seven cases, K \le 10^6.

Output Specification

For each test case, your program should output one integer representing the restaurant Ava will eat at on the K^{th} day.

Sample Input

2 5 4
20 17
5 4 7
1 2 4 8 16
4 8 100
3 22 20 14

Sample Output

2
5
3

Note: Only 3 cases are shown in this sample.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments

There are no comments at the moment.