## Description

ZSoft Corp. is a software company in GaoKe Hall. And the workers in the hall are very hard-working. But the elevator in that hall always drives them crazy. Why? Because there is only one elevator in GaoKe Hall, while there are hundreds of companies in it. Every morning, people must waste a lot of time waiting for the elevator.

Hal, a smart guy in ZSoft, wants to change this situation. He wants to find a way to make the elevator work more effectively. But it’s not an easy job.

There are 31 floors in GaoKe Hall. It takes 4 seconds for the elevator to raise one floor. It means:

It costs (31-1)*4=120 seconds if the elevator goes from the 1st floor to the 31st floor without stop. And the elevator stops 10 second once. So, if the elevator stops at each floor, it will cost 30*4+29*10 = 410 seconds (It is not necessary to calculate the stopping time at 31st floor). In another way, it takes 20 seconds for the workers to go up or down one floor. It takes 30*20 = 600 seconds for them to walk from the 1st floor to the 31st floor. Obviously, it is not a good idea. So some people choose to use the elevator to get a floor which is the nearest to their office.

After thinking over for a long time, Hal finally found a way to improve this situation. He told the elevator man his idea: First, the elevator man asks the people which floors they want to go. He will then design a stopping plan which minimize the time the last person need to arrive the floor where his office locates. For example, if the elevator is required to stop at the 4th, 5th and 10th floor,the stopping plan would be: the elevator stops at 4th and 10th floor. Because the elevator will arrive 4th floor at 3*4 = 12 second, then it will stop 10 seconds, then it will arrive 10th floor at 3*4+10+6*4 = 46 second. People who want to go 4th floor will reach their office at 12 second, people who want to go to 5th floor will reach at 12+20 = 32 second and people who want to go to 10th floor will reach at 46 second. Therefore it takes 46 seconds for the last person to reach his office. It is a good deal for all people.

Now, you are supposed to write a program to help the elevator man to design the stopping plan,which minimize the time the last person needs to arrive at his floor.

## Input

The input consists of several testcases. Each testcase is in a single line as the following: n f1 f2 … fn

It means, there are totally n floors at which the elevator need to stop, and n = 0 means no testcases any more. f1 f2 … fn are the floors at which the elevator is to be stopped (n <= 30, 2 <= f1 < f2 … fn <= 31). Every number is separated by a single space.

## Output

For each testcase, output the time the last reading person needs in the first line and the stopping floors in the second line. Please note that there is a summary of the floors at the head of the second line. There may be several solutions, any appropriate one is accepted. No extra spaces are allowed.

## Source

Asia Guangzhou 2003

## Solution

1. 电梯决定停在第k层时：要去 1..k 层的人应选择在这时下电梯，这样一定可以得到当前决策下的一个最优解。如图：

1. 电梯在第k层时，若要去 k+r 层的人选择在这时下电梯，则：要去k+1..k+r-1层的人也应选择在此时下电梯，这样一定可以得到当前决策下的一个最优解。如图：

f[i,j]表示电梯在第i层，电梯上有要去楼层最高的j个人时，电梯上的人全部到达各自楼层所需的最短时间

f[i,j] = min{ max(t1, t2) } (0<=k<=j)

t1 = f[i+1, k] + 电梯停留时间 + 电梯上升一层所用时间

t2 = max{ |d[l] – i| * 人爬一层楼所用时间 } ( k+1<=l<=j )


#include <iostream>
using std::cin;
using std::cout;
using std::endl;

#include <cstring>
using std::memset;

#include <algorithm>
using std::max;

#include <cmath>
using std::abs;

#include <limits>
using std::numeric_limits;

#include <vector>
using std::vector;

const int maxN = 30, maxF = 31;
const int ve = 4, st = 10, vw = 20; // 电梯上一层所需时间；电梯停一层所需时间；人走一层所需时间

int n, f[maxN + 1];

bool input()
{
cin >> n;
if (n==0) return false;

// 注意：f[1..n]中楼层数从高到底排列
for (int i = n; i>=1; --i)
cin >> f[i];

return true;
}

int dp[maxF + 1][maxN + 1], nextJ[maxF + 1][maxN + 1];

// 现在电梯在第currF层，第L到第R人离开电梯
// 函数返回这些离开电梯的人中最晚到达目的楼层所需的时间
int tLeave(int currF, int l, int r)
{
if (l>r)  return 0;
// 仅需考虑两端
return max(abs(currF-f[l]), abs(currF-f[r])) * vw;
}

// 现在电梯在第i层，电梯里本来有j个人，在要下电梯的人离开后还剩jj个人
// 函数返回这些留在电梯里的人中最晚到达目的楼层所需的时间
int tStay(int i, int j, int jj)
{
// 没人下电梯
if (j==jj)
return dp[i+1][jj] + ve;
// 所有人都离开电梯
else if (jj==0)
return 0;
// 第1层不计算电梯停留时间
else if (i==1)
return dp[i+1][jj] + ve;
//普通情况
else
return dp[i+1][jj] + ve + st;
}

void calculate()
{
// 边界：电梯在顶楼时所有人都必须下电梯
int topFloor = f[1];
for (int j = 1; j<=n; ++j)
dp[topFloor][j] = tLeave(topFloor,1,j);

for (int i = topFloor - 1; i>=1; --i)
for (int j = 1; j<=n; ++j)
{
dp[i][j] = numeric_limits<int>::max();
for (int jj = 0; jj <= j; ++jj)
{
// 取离开电梯的人和留下的人中的最晚到达者
int tmp = max(tStay(i,j,jj),tLeave(i,jj+1,j));
if (dp[i][j] > tmp)
{
dp[i][j] = tmp;
nextJ[i][j] = jj;
}
}
}
cout << dp[1][n] << endl;
}

void rebuildSolution()
{
vector<int> stops;
int j = nextJ[1][n], topFloor = f[1];
for (int i = 2; i<=topFloor; ++i)
if (nextJ[i][j]!=j)
{
stops.push_back(i);
j = nextJ[i][j];
if (j==0) break;
}

cout << stops.size();
for (int i = 0; i!=stops.size(); ++i)
cout << ' ' << stops[i];
cout << endl;
}

void solve()
{
memset(dp,0,sizeof(dp));
memset(nextJ,0,sizeof(nextJ));
calculate();
rebuildSolution();
}

int main()
{
while (input())
solve();
}