158. Commuter Train
time limit per test: 0.5
sec.
memory limit per test: 65536
KB
input: standard input
output: standard output
You might have noticed that bus drivers sometimes pass by passengers waiting for the bus and stop at a place where the distance from the people to the bus doors is maximal. We don't know exact reasons of such behaviour, probably, this is done not because of some special wickedness of the driver but in order to allow passengers in the vehicle to get oR quicker. However, we know that in one country the government decided to implement automatic driving system on their commuter railroads. Among other features, this system is intended to automatically stop commuter trains at stations. A computer in the train is connected to a special radar, which determines passenger positions at the station platform. The computer decides where to stop the train in order to maximize the sum of the distances from each passenger to the closest door. All the hardware is ready, but the software project is late (transport problems). Your task is to implement this function for this software project.
More precisely, the station platform has length 0 < L <= 5000. There are 0 < M <= 300 passengers at the platform. Each passenger p has position Pp (0 <= P1 <= ... <= PM <= L)  the distance from the platform beginning to the passenger. There are 0 < N <= 300 doors in the train. Each door d has position Dd (0 = D1 < D2 < ... < DN <= L)  the distance from it to the door 1. The door width and the passenger sizes are not taken into account. For simplicity assume that the distance between a passenger i and a train door j is dist(i, j, S) = Dj + S  Pi, where S is train position  the distance between the first door and the beginning of the platform. Remember that the train must stop so that no door is outside of the platform.
Input
The file contains integer numbers separated by spaces and/or line feeds. At the beginning of the file there is the station description (L, M, and P1 ... PM), followed by the train description (N and D2 ... DN).
Output
You should output two numbers  the train position S, at which the maximal possible sum of the minimal distances between the passengers and the doors can be achieved and the sum itself. If there are many such train positions  output any one.
Sample test(s)
Input
Sample input #1
6
2
0 4
2
4
Sample input #2
4
5
0 1 2 3 4
4
1 2 3
Output
Sample output #1
2 4
Sample output #2
0.5 2.5
Note
You can download pdf version of this task
here
Author:  Andrew Lopatin, Nikolay Durov

Resource:  ACM ICPC 20022003 NEERC, Northern Subregion

Date:  November, 2002

Server time: 20160901 01:38:40  Online Contester Team © 2002  2016. All rights reserved. 

