[Login|Register]
Problems

Status

Rank

Problem 1220
Perfect Deployment
Time Limit: 1000ms
Memory Limit: 65536kb
Description
Alipay has many independent systems. These systems should be deployed in every Wednesday, but only one system can be deployed at the same time, the others can only wait. Now we need your help to design a plan to reduce the system's average waiting time. Known as follow:
1.All the systems begin to be deployed at the same same, and this time is called STARTING TIME. this is reasonable because engineers start to work at 9:00.
2. Once a system begin to be deployed, it will not stop until finishing.
3. The release time of each system is determined.
4. Each system's waiting time will vary with the planning, the goal is to make the average waiting time smallest.
Now it's your time to solve it.
Input
There are several cases. Every case begins with n(1<=n<=100), the number of system. The next n lines each will start with a name, and following by a number denoting the time the deployment will cost.
The input is ended by n = 0;
Output
For each case print the average waiting time, the results are rounded to 3 digits after the decimal point.
Sample Input
3
authcenter 10
personal 20
cashier 30
0
Sample Output
33.333
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.5ms with 1 query(s).