ECOO '17 R2 P3 - Lunch Time

View as PDF

Submit solution

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

Author:
Problem type

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 Specifications

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 Specifications

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.