首页 > ACM题库 > HDU-杭电 > HDU 3269-P2P File Sharing System-模拟-[解题报告]HOJ
2014
03-13

HDU 3269-P2P File Sharing System-模拟-[解题报告]HOJ

P2P File Sharing System

问题描述 :

Peer-to-peer(P2P) computing technology has been widely used on the Internet to exchange data. A lot of P2P file sharing systems exist and gain much popularity in nowadays.

Let’s consider a simplified model of P2P file sharing system: There are many computers in the system, and they can receive data from or send data to others. To simplify the problem, let’s assume that there is just ONE large file which is of our concern in the system. Some computers already have the whole file (we call them "servers" and some don’t(we call them "clients". Every client needs to download the file from servers. When a client gets the WHOLE file, it becomes a server.

These computers are not always online. An online client will down load the file from all online servers. Different servers send data of different parts of the file to a client, so the client can download the file faster.

Now given the transfer speed between each pair of computers, what time is every computer online or offline, and which computers are servers at the beginning, please analyze the running of the system in a period of time.

输入:

The first line contains an integer indicating the number of test cases.
For each test case:
Line 1: It contains two positive integers: n and T(n<=20, T<=1000) meaning that there are n computers in the system numbered from 1 to n, and you task is to figure out that how many percentage of the file does every computer gets after T seconds from the beginning.
Line 2: It contains two positive integers: k and S (k<=n, S<=220) meaning that at the beginning there are k servers, and the size of the file of our concern is S (KB).
Line 3: It contains k integers. It’s a list of all servers’No.
Line 4 ~ n+3: These n lines form a matrix of size n*n. The j-th integer in the i-th row of the matrix represents the transfer speed (in KB/s, no more than 210) between computer i and computer j (i and j start from 1). The matrix is symmetrical and the integers on the diagonal are meaningless.
Line n+4 ~ 2n+3: Each line contains an online/offline pattern for a computer in the following format( These lines are in the ascending order of computer No.) :
t online_time1 offline_time1 online_time1 offline_time2 … online_timet offline_timet
t is an integer no more than 10 and the time given are all non-negative integers and in ascending order. During the time between online_timei and offline_timei, the computer is online and can download data from other computers or send data to other computers.
Line 2n+4: It contains one positive integer m, representing the number of download actions in the system.
Line 2n+5 ~ 2n+m+4: Each line contains two integers representing a download action in the following format:
download_timei computer_idi
At time download_timei, the computer computer_idi starts to download the file. 0<= download_timei <=T, 1<= computer_idi <=n. These lines are given in non-descending order of time. It’s guaranteed that servers never try to download the file. It’s ensured that at time download_timei the computer computer_idi is online (Though it’s possible that it instantly go offline after issuing a download command).

When a client starts to download, it will try to connect to all servers and download data simultaneously from online servers. The client’s download speed is the sum of all connections. We assume the construction of a connection to be instant and cost no time. Only data transfer is time consuming.

When a client goes offline, unfinished download task will be saved and continued when it’s online next time. If a server goes online, all computers that are currently downloading will connect to it and download data from it. What’s more, when a client becomes a server, it begins to send data to clients immediately. NOTE: To simplify the problem, time used to download a file should be rounded up to integer(If the file size is 6KB and download speed is 5KB/s, the download task will cost 2 seconds instead of 1.2 seconds —– 5KB for the first second and 1KB for the next second).

Please note that all times given above are in seconds.

输出:

The first line contains an integer indicating the number of test cases.
For each test case:
Line 1: It contains two positive integers: n and T(n<=20, T<=1000) meaning that there are n computers in the system numbered from 1 to n, and you task is to figure out that how many percentage of the file does every computer gets after T seconds from the beginning.
Line 2: It contains two positive integers: k and S (k<=n, S<=220) meaning that at the beginning there are k servers, and the size of the file of our concern is S (KB).
Line 3: It contains k integers. It’s a list of all servers’No.
Line 4 ~ n+3: These n lines form a matrix of size n*n. The j-th integer in the i-th row of the matrix represents the transfer speed (in KB/s, no more than 210) between computer i and computer j (i and j start from 1). The matrix is symmetrical and the integers on the diagonal are meaningless.
Line n+4 ~ 2n+3: Each line contains an online/offline pattern for a computer in the following format( These lines are in the ascending order of computer No.) :
t online_time1 offline_time1 online_time1 offline_time2 … online_timet offline_timet
t is an integer no more than 10 and the time given are all non-negative integers and in ascending order. During the time between online_timei and offline_timei, the computer is online and can download data from other computers or send data to other computers.
Line 2n+4: It contains one positive integer m, representing the number of download actions in the system.
Line 2n+5 ~ 2n+m+4: Each line contains two integers representing a download action in the following format:
download_timei computer_idi
At time download_timei, the computer computer_idi starts to download the file. 0<= download_timei <=T, 1<= computer_idi <=n. These lines are given in non-descending order of time. It’s guaranteed that servers never try to download the file. It’s ensured that at time download_timei the computer computer_idi is online (Though it’s possible that it instantly go offline after issuing a download command).

When a client starts to download, it will try to connect to all servers and download data simultaneously from online servers. The client’s download speed is the sum of all connections. We assume the construction of a connection to be instant and cost no time. Only data transfer is time consuming.

When a client goes offline, unfinished download task will be saved and continued when it’s online next time. If a server goes online, all computers that are currently downloading will connect to it and download data from it. What’s more, when a client becomes a server, it begins to send data to clients immediately. NOTE: To simplify the problem, time used to download a file should be rounded up to integer(If the file size is 6KB and download speed is 5KB/s, the download task will cost 2 seconds instead of 1.2 seconds —– 5KB for the first second and 1KB for the next second).

Please note that all times given above are in seconds.

样例输入:

Sample 1
1
2 50
1 1024
1
0 10
10 0
1 0 50
1 10 40
1
10 2

Sample 2
1
4 500
2 200
2 3
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
2 0 200 300 500
1 100 200
1 200 400
1 301 500
2
0 1
301 4

样例输出:

100%
29%
Hint
There are 2 computers. The file size is 1024 KB and Computer 1 is a server at the beginning. At time 10, computer 2 start to download that file from computer 1 until it goes offline at time 40. Totally 10KB/s * 30s = 300KB is downloaded. 300/1024 ≈ 29%.
100% 100% 100% 99%


P2P File Sharing SystemView Code

#include<stdio.h>
#include<string.h>
int T,cases,n,k,m,fsize;
int isver[25];
int speed[25][25];
int online[25][1010];
int get[25];
int start[25];
void init()
{
    memset(isver,0,sizeof(isver));
    memset(online,0,sizeof(online));
    memset(get,0,sizeof(get));
 memset(start,-1,sizeof(start));
}
int main()
{
    int i,j,k,temp,t;
    int s,end;
    int ti,id;
    int tspeed;
    scanf("%d",&cases);
    while(cases--)
    {
       init();
       scanf("%d%d",&n,&T);
       scanf("%d%d",&k,&fsize);
       for(i=0;i<k;i++)
       {
        scanf("%d",&temp);
        isver[temp-1]=1;
  get[temp-1]=fsize;
       }
       for(i=0;i<n;i++)
         for(j=0;j<n;j++)
            scanf("%d",&speed[i][j]);
       for(i=0;i<n;i++)
       {
            scanf("%d",&t);
            for(j=0;j<t;j++)
            {
                scanf("%d%d",&s,&end);
                for(k=s;k<end;k++)
                  online[i][k]=1;
            }
       }
       scanf("%d",&m);
       for(i=1;i<=m;i++)
       {
             scanf("%d%d",&ti,&id);
    id--;
             if(start[id]==-1||start[id]>ti)
     start[id]=ti;
       }
       for(i=0;i<T;i++)
    {
     for(j=0;j<n;j++)
     {
      if(!isver[j]&&online[j][i]&&start[j]!=-1&&start[j]<=i)
      {
       for(k=0;k<n;k++)
        if(isver[k]&&online[k][i])
         get[j]+=speed[j][k];
      }
     }
     for(j=0;j<n;j++)
      if(!isver[j]&&get[j]>=fsize)
      {
       get[j]=fsize;
       isver[j]=1;
      }
    }
       for(i=0;i<n;i++)
     printf("%d%%\n",get[i]*100/fsize);
    }
    return 0;
}

参考:http://www.cnblogs.com/wuyiqi/archive/2011/10/11/2207768.html


  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。