UFAST - Unite Fast
Getting the line ready, is the process of agents moving from their current positions in order to get the network fully connected. That is, from every agent to every other agent, there is a communication path.
The agent’s final positions (in two cases that are going to follow) are decided by a programmer, who watches the scene from above and instructs each agent of the time to move and the final position to move to. Each agent moves a unit distance in unit time.
We need to find the minimal time taken for the programmer to “get the line ready” if he moves the agents:
1. Independently: In other words, every agent moves to their final
position without waiting for any other agent; all agents are told of
their final positions at time zero.
2. Sequentially: In this the agents form a definite sequence of movement. No two agents are moving at the same time.
Input
T – number of test cases. For each test case :
N D – where N is the number of agents, D is the maximal communication distance
The i-th line, of the N-lines that follow gives the position of the i-th agent on the road currently.
Output
For each test case, output two integers;
1st – minimal time taken to unite if they move independently
2nd – minimal time taken to unite if they move sequentially
Constraints:
T<=20
1<=N, D<=100 ;
Each agent's initial position is between 0 and 1000.
Example
Sample Input: 2 4 3 10 20 30 35 5 3 1 2 3 4 30 Sample Output: 8 23 12 23
Added by: | Prasanna |
Date: | 2006-01-13 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS PERL6 VB.NET |
Resource: | ByteCode '06 |