2014
03-09

Jiajia downloads a lot, a lot more than you can even imagine. Some say that he starts downloading up to 20,000 files together. If 20,000 files try to share a limited bandwidth then it will be a big hazard and no files will be downloaded properly. That is why, he uses a download manager.

2. The available bandwidth is equally shared by the all the files that are being downloaded. When a file is completely downloaded its bandwidth is instantaneously given to the next file. If there are no more files left except the files that are being downloaded, this bandwidth is immediately shared equally by all remaining files that are being downloaded.

Given the size and completed percentage of each file, your task is to intelligently simulate the behavior of the download manager to find the total time required to download all the files.

6 3 90
100.00 90
40.40 70
60.30 70
40.40 80
40.40 85
40.40 88
1 1 56
12.34 100
0 0 0

Case 1: 0.66

Case 2: 0.00

HintExplanation

In the first sample, there are 6 files and the download manager can download 3 files simultaneously. The size of the smallest file is 40.40 Megabyte but there are
four such files (2nd, 4th, 5th and 6th files). So the download manager chooses the 6th, 5th and 4th files for download as they have less bytes remaining. All these
files get equal bandwidth (30.00 Megabyte/Sec). Of these three files the 8th file is finished first. So instantaneously the 2nd file starts downloading. Then, 5th file
is finished. So the next larger file (3rd file) starts downloading. This process goes on until all files are downloaded. 

#include<cstdio>

int main()
{
int T,n,cnt = 1,B;
while(scanf("%d%d%d",&T,&n,&B),(T || n || B))
{

double s,p,sum = 0;
while(T--)
{
scanf("%lf%lf", &s, &p);
sum += s*(1.0-p/100.0);
}
printf("Case %d: %.2f\n\n",cnt++,sum/(B*1.0));
}
return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define N 200010

struct Node
{
double size,rest;
int p;
};
Node node[N];

int cmp(Node a, Node b)
{
if(a.size != b.size)
return a.size < b.size;
return a.p > b.p;
}

int main()
{
int T,n,B,cas = 1;
while(scanf("%d%d%d", &T,&n,&B) && (T||n||B))
{
for(int i = 1; i <= T; i++)
{
scanf("%lf%d", &node[i].size,&node[i].p);
node[i].rest = 1.0*node[i].size*(1.0-0.01*node[i].p);
}
sort(node+1,node+1+T,cmp);	//按下载要求来排列下载次序
double time = 0,M = (double)B;
for(int j = 1; j <= T; j++)
{
int q = j+n-1;
if(q > T)				//如果剩余的个数少于n个，平均带宽为M/（T-j+1)
{
time += (node[j].rest / (M/((T-j+1)*1.0)));
for(int i = j+1 ; i <= T ; i++)
{
node[i].rest -= node[j].rest;
}
}
else					//如果剩余个数不小于n个，剩余带宽为M/n
{
time += (node[j].rest / (M/(n*1.0)));
for(int i = j+1 ; i <= q ; i++)
{
node[i].rest -= node[j].rest;
}
}
}
printf("Case %d: %.2f\n\n",cas++,time);
}
}

1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.