A Subtle Surf

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem type
University of Toronto ACM-ICPC Tryouts 2013

Alice has received an invitation from Bob to watch some TV on D (1 \le D \le 100) days! Though spending time with him is nice, she's more concerned about exactly what channels they'll be watching. After all, being a guy, Bob is sure to be interested in viewing less sophisticated programs than she is.

On each day, a different set of N (1 \le N \le 100\,000) channels are available, numbered 1\ldots N. Each channel i has a girliness value of G_{i} (0 \le G_{i} \le 10^{9}) associated with it, indicating how much Alice would like to watch it. When she arrives at Bob's house, the TV is set to channel 1, but she'd like to surf to a channel with maximal girliness, and as quickly as possible.

Alice wants to be subtle about her channel surfing, however. She believes that Bob may notice if they stay on any channel for less than T (1 \le T \le 1\,000) seconds before switching, or if the girliness value of the new channel is more than C (1 \le C \le 10^{9}) greater than that of the current one. She needs a plan of action to maximize the girliness of the channel they end up watching, while minimizing the amount of time it'll take her to surf to such a channel.

Input Specification

Line 1: 1 integer, D

For each day:
Line 1: 3 integers, N, C, and T
Line 2: N integers, G_{1\ldots N}

Output Specification

For each day, output 2 integers, the maximum channel girliness which Alice can surf to, and the minimum number of seconds required to arrive at a channel with this girliness, respectively.

Sample Input

6 3 5
3 4 0 8 12 6
4 1 2
5 7 7 5

Sample Output

8 10
5 0

Explanation of Sample

On the first day, Alice should switch to channel 6 after 5 seconds, and to channel 4 after another 5 seconds.
On the second day, Alice can't surf to either channel 2 or 3, so she should stay on channel 1.


There are no comments at the moment.