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 Gi (0 ≤ Gi ≤ 109) 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 ≤ 109) 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.
Line 1: 1 integer, D
For each day:
Line 1: 3 integers, N, C, and T
Line 2: N integers, G1..N
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.
2 6 3 5 3 4 0 8 12 6 4 1 2 5 7 7 5
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.
Point Value: 10
Time Limit: 2.00s
Memory Limit: 64M
Added: Jul 08, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3