A new government has been elected in Siruseri and has begun the usual process of shuffling all the officials appointed by the previous regime. One of the departments affected is the railways.
The railway network in Siruseri is just a single straight line, with N stations. Of these N stations, L have station masters, distributed at various stations along the line. The government has decided to transfer all station masters so as to keep them as far apart as possible. Unfortunately for the government, there is a clause in the contract negotiated with the railway union by which a station master may be transferred at most K stations from his current posting. The task before the government is to achieve its goal of transferring station masters to maximize the minimum distance between any pair within the restrictions of the contract.
For instance, suppose there are 10 stations, numbered 1,2,...,10, and there are 3 station masters, currently assigned to stations 5, 7 and 8. Further, let us suppose that no station master can move more than 2 stations away from the current station. Then, the best the government can do is to move the station master at station 5 to station 3 and the station master at station 8 to station 10. In the new arrangement, the station masters are at stations 3, 7 and 10 and the minimum gap is 2 stations, between stations 7 and 10. (Note that, in addition, the station master at station 7 could be moved to station 6, in which case the minimum gap of 2 would be betweens stations 3 and 6.)
Input bounds: L ≤ 105, N and K are integers.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky