ACARGO - Accumulate Cargo

no tags 

A cargo shipment containing N (1 <= N <= 105) boxes, has just arrived and it requires some regrouping. All the cargo is currently placed on a long circular conveyor belt of length L metres (1 <= L <= 109), which you can control and perform the following operations.

  • Rotate the wheel clock wise or anti-clockwise (free of cost).
  • Hold the cargo at some point and not let it move, while the belt is rolling. This causes the cargo behind it to come closer to this cargo by one step. Any consecutive sequence of cargo is grouped together and called as a luggage. The aim of the program is to group all cargo as a single luggage. Now the cost of this holding operation for one second is equal to the weight of the luggage that is held fixed. Also please note that you can hold the luggage only at ends of the luggage and never at inbetween points.
Each unit of cargo weighs exactly one Kg. The conveyor belt rotates at a speed of one meters per second.
This cost function directly reflects the human effort required to group the cargo. Workers would be happy if you can write a program that prints the minimal required effort to group the cargo, assuming an intelligent sequence of operations.


Input Format:
The input file consists of multiple testcases.
The first line of each testcase contains two integers, N and L.
The following N lines contain one integer each specifying the position of the ith cargo on the belt. The positions will be between 0 & L-1.
Input terminates with a line containing N=0 and L=0 which must not be processed.

Output Format:
For each testcase print one integer in a single line, which is the minimal required cost for grouping all the cargo into a single luggage.

Sample Input:
3 5
0
1
3
2 3
0
1
5 20
2
7
12
9
13
0 0
Sample Output:
1
0
10
NOTE: Please use 64-bit integers.

hide comments
samratks_7: 2016-10-14 17:06:22

Can anyone explain the problem stat clearly??


Added by:Prasanna
Date:2007-10-08
Time limit:0.100s-1.621s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:NITT ACM ICPC Local Contest 2007 [Idea from a Topcoder problem]