University of Toronto ACM-ICPC Tryouts 2013

C: A Subtle Surf

Alice has received an invitation from Bob to watch some TV on D (1 ≤ D ≤ 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 ≤ N ≤ 100,000) channels are available, numbered 1..N. Each channel i has a girliness value of G_i (0 ≤ G_i ≤ 10⁹) 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 ≤ T ≤ 1000) seconds before switching, or if the girliness value of the new channel is more than C (1 ≤ C ≤ 10⁹) 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

Line 1: 1 integer, D

For each day:
Line 1: 3 integers, N, C, and T
Line 2: N integers, G_1..N

Output

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

2
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.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 64M
Added: Jul 08, 2014
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)