Backup Plan
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 93 Accepted Submission(s): 36
Special Judge
Every time someone wants to execute queries on a certain database, he will send a request to the first server in the list. If it's dead, he will simply turn to the next one. Otherwise a working copy of the database is found, and this copy is called active.
Now, given N and M, Makomuno wants to find a permutation for each database which could assure that all servers are load-balanced. Moreover, Makomuno hopes the system will be load-balanced even if exactly one server is broken.
Note that if we call the number of active copies on i-th server Ai, then load-balanced means max∣Ai - Aj∣≤1 for any i and j in non broken servers set. We won't consider broken servers in this case.
Each test case has one line containing two integer N ( 2≤N≤100) and M ( 1≤M≤100).
1 5 4 2 3
3 5 2 4 1
In the sample test case, the active copies of these databases are on server 2,1 and 3 in normal state. A = {1,1,1,0,0}
If server 1 or 3 has broken, server 5 will take its work. In case we lost server 2, the second database will use server 4 instead. A = {1,BROKEN,1,1,0}
It's clear that in any case this system is load-balanced according to the plan in sample output.
题目意思很难懂,自己去理解吧、
就是要构造出一个m*n的矩阵
我的做法就是
1) n>=m
那么第一列就放1,2,....m
第二列放n n n n n n n n (如果n==m的情况,那么在第一列是n的时候放n-1).
其余列放没有在第一列和第二列出现的既可。
2) n < m
这种情况:
第一列的方法是1 2 3 ....n 1 2 3 ....n 1 2 3...这样循环
第二列。
对于第1列放1的行,就是n*k+1(k=0,1,2...)行,从n,n-1,n-2,...这样循环放,遇到1就跳过。
对于放2的行一样处理,遇到2跳过
对于其它数也一样。
然后其余列只有和前两列不同既可
/* **********************************************
Author : kuangbin
Created Time: 2013/8/13 13:34:52
File Name : F:\2013ACM练习\2013多校7\1006.cpp
*********************************************** */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
using namespace std;
int a[][];
bool used[];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,m;
while(scanf("%d%d",&n,&m) == )
{
if(n >= m)
{
for(int i = ;i <= m;i++)
{
a[i][] = i;
a[i][] = n;
if(a[i][]==n)a[i][] = n-;
memset(used,false,sizeof(used));
used[a[i][]] = used[a[i][]] = true;
int t = ;
for(int j = ;j <= n;j++)
{
while(used[t])t++;
a[i][j] = t++;
}
}
}
else
{
int t = ;
for(int i = ;i <= m;i++)
{
a[i][] = t++;
if(t > n)t = ;
}
for(int i = ;i <= n;i++)
{
if(i < n)t = n;
else t = n-;
for(int j = ;j*n+i <= m;j++)
{
a[j*n+i][] = t;
t--;
// printf("%d %d %d\n",i,j,t);
if(t == )t = n;
if(t == i)t--;
if(t==)t=n;
} }
for(int i = ;i <= m;i++)
{
memset(used,false,sizeof(used));
used[a[i][]] = used[a[i][]] = true;
int t = ;
for(int j = ;j <= n;j++)
{
while(used[t])t++;
a[i][j] = t++;
}
}
}
for(int i = ;i <= m;i++)
{
for(int j = ;j <= n;j++)
{
printf("%d",a[i][j]);
if(j < n)printf(" ");
else printf("\n");
}
}
}
return ;
}