zoj
DreamGrid, the king of Gridland, is making a knight tournament. There are knights, numbered from 1 to , participating in the tournament. The rules of the tournament are listed as follows:
- The tournament consists of rounds. Each round consists of several duels. Each duel hAPPens between exactly two knights.
- Each knight must participate in exactly one duel during each round.
- For each pair of knights, there can be at most one duel between them during all the rounds.
- Let , , and , be four distinct integers. If
- Knight fights against knight during round , and
- Knight fights against knight during round , and
- Knight fights against knight during round ,
As DreamGrid's general, you are asked to write a program to arrange all the duels in all the rounds, so that the resulting arrangement satisfies the rules above.
Input
There are multiple test cases. The first line of the input is an integer , indicating the number of test cases. For each test case:
The first and only line contains two integers and (), indicating the number of knights participating in the tournament and the number of rounds.
It's guaranteed that neither the sum of nor the sum of in all test cases will exceed 5000.
Output
For each test case:
-
If it's possible to make a valid arrangement, output lines. On the -th line, output integers separated by one space, indicating that in the -th round, knight will fight against knight for all .
If there are multiple valid answers, output the lexicographically smallest answer.
Consider two answers and , let's denote as the -th integer on the -th line in answer , and as the -th integer on the -th line in answer . Answer is lexicographically smaller than answer , if there exists two integers () and (), such that
- for all and , , and
- for all , , and finally .
- If it's impossible to make a valid arrangement, output "Impossible" (without quotes) in one line.
Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!
Sample Input
2 3 1 4 3
Sample Output
Impossible 2 1 4 3 3 4 1 2 4 3 2 1
题解：我们另第一行为1 2 3 4 5 6 7 8 ... 写出几个可以看出
1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 3 4 写到这里是不是就可以看出规律了 就是 先是两个互换 然后接下来 两个 对应上面左半部分和右半部分的逆序
最后4个为 上4个的逆序 然后对应一个n 我们可以进行多少次战争呢 就是 lowbit(n) - 1
#include <iOStream>
#include<cstdio>
using namespace std;
int n,k;
int dp[1100][1100];
void dfs(int l,int r,int cur)
{
if(cur==1)
{
for(int i=1;i<=n;i++)
dp[cur][i]=i;
return;
}
dfs(l,(l+r)/2,cur/2);
for(int i=cur/2+1;i<=cur;i++)
{
for(int j=1;j<=n;j+=cur)
{
int k=j+cur-1;
for(int mm=j;mm<j+cur;mm++)
{
dp[i][mm]=dp[cur/2-(i-cur/2-1)][k-(mm-j)];
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
int m=n;
int flag=1;
int cnt=0;
while((m&1) != 1)
{
cnt++;
m>>=1;
}
if(flag&&(1<<cnt)-1<k) flag=0;
if(!flag) printf("Impossible\n");
else
{
dfs(1,n,(1<<cnt));
for(int i=2;i<=k+1;i++)
{
for(int j=1;j<=n;j++)
printf("%d%c",dp[i][j]," \n"[j==n]);
}
}
}
return 0;
}
相关阅读
description 因为小Y 是知名的白富美，所以自然也有很多的追求者，这一天这些追求者打算进行一次游戏来踢出一些人，小R 自然也参加了。
https://vjudge.net/problem/ZOJ-3981题意：第一行三个数字n, m, q表示有m个座位围成一个环，n个队伍，q次A题接下来n个数表示n个队伍所
description 邮局需要你来帮助他们为某个邮递员设计出一条能够穿过那遥远乡村的所有村子和小路至少一次的邮路（输入数据将会保证这
题意 从nnn个人中选kkk个人，问被选到的概率。思路 根据数学知识可知答案为k/nk/nk/n。代码 无。
没有传送门 题目大意 样例输入 样例输出 样例解释（原题没有） 考场上的思路 参考代码 没有传送门 题目大意 A 和