C. Minimum Ties-Educational Codeforces Round 104 (Rated for Div. 2)

Minimum Ties - 洛谷

Problem - 1487C - Codeforces

C. Minimum Ties

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

A big football championship will occur soon! nn teams will compete in it, and each pair of teams will play exactly one game against each other.

There are two possible outcomes of a game:

• the game may result in a tie, then both teams get 11 point;
• one team might win in a game, then the winning team gets 33 points and the losing team gets 00 points.

The score of a team is the number of points it gained during all games that it played.

You are interested in a hypothetical situation when all teams get the same score at the end of the championship. A simple example of that situation is when all games result in ties, but you want to minimize the number of ties as well.

Your task is to describe a situation (choose the result of each game) so that all teams get the same score, and the number of ties is the minimum possible.

Input

The first line contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases.

Then the test cases follow. Each test case is described by one line containing one integer nn (2≤n≤1002≤n≤100) — the number of teams.

Output

For each test case, print n(n−1)2n(n−1)2 integers describing the results of the games in the following order: the first integer should correspond to the match between team 11 and team 22, the second — between team 11 and team 33, then 11 and 44, ..., 11 and nn, 22 and 33, 22 and 44, ..., 22 and nn, and so on, until the game between the team n−1n−1 and the team nn.

The integer corresponding to the game between the team xx and the team yy should be 11 if xx wins, −1−1 if yy wins, or 00 if the game results in a tie.

All teams should get the same score, and the number of ties should be the minimum possible. If there are multiple optimal answers, print any of them. It can be shown that there always exists a way to make all teams have the same score.

Example

input

Copy

2
2
3

output

Copy

0 
1 -1 1 

Note

In the first test case of the example, both teams get 11 point since the game between them is a tie.

In the second test case of the example, team 11 defeats team 22 (team 11 gets 33 points), team 11 loses to team 33 (team 33 gets 33 points), and team 22 wins against team 33 (team 22 gets 33 points).

因为所有球队积分相同，故得分总和是kn,且进行 n*(n-1)/2次比赛，故可以设胜负场x,平局y

注意数学推导的时候，实际问题中的除号一定不能看成整除！！本题考察点就在是否整除上

3x+2y=kn

x+y=n*(n-1)/2

得

x=n*(n-1)/2-y

3(n*(n-1)/2-y) +2y =kn

3n*(n-1)/2 -y=kn

y=n*(3n-3)/2 -kn   //提出定值n

 =n* (  ( 3(n-1)-2k )/2 - ) 

等式右边在满足是整数的情况下，k的取值应该让y最小

n如果是偶数  3(n-1)-2k  = 2t  (t=1,2,..)  

k =( 3(n-1)-2t  )/2     t=1时k最大，y最小 

 y=n*(3n-3)/2 -n ( (3n-3)-2  )/2 =1

n是奇数,显然y=0

然后考察构造技巧，其实CFn^2类构造填数题套路就是n^2直接扫描构造，为了保证答案正确，多设置标记数组即可，比如book[][]代表是否对决，ping,sheng,shu分别代表剩余平局，胜局，输局个数，严格把控即可

# include<iostream>
# include<complex.h>
# include<string.h>
# include<cstring>
# include<vector>
# include<algorithm>
# include<iomanip>

using namespace std;
typedef complex<double>cp;
# define mod 9999991
typedef long long int  ll;

int book[110][110];
bool ping[110];
int ying[110];
int shu[110];

int sta[110];
int ans[110][110];

int n;

void work1(int cnt)  //每个队伍赢cnt次
{

    memset(book,0,sizeof(book));


    for(int i=1;i<=n;i++)
    {
        book[i][i]=1;

    }

    for(int i=1;i<=n;i++)
    {
        ying[i]=cnt;
        shu[i]=n-1-cnt;

    }

    for(int i=1;i<=n;i++)
    {
        int len=0;

        for(int j=1;j<=n;j++)
        {

            if(!book[i][j]&&!book[j][i])//没有对决
            {
                if(shu[j])//还能再输
                {
                    if(len+1<=ying[i])
                    {
                        len++;

                        shu[j]--;

                        book[i][j]=1;

                        book[j][i]=1;



                        ans[i][j]=1;

                        ans[j][i]=-1;

                    }
                }
            }
        }


    }
}

void work2(int cnt)
{

    memset(book,0,sizeof(book));

    for(int i=1;i<=n;i++)
    {
        book[i][i]=1;
        ping[i]=0;

    }

    for(int i=1;i<=n;i++)
    {
        ying[i]=cnt;
        shu[i]=n-2-cnt;

    }

    for(int i=1;i<=n;i++)
    {
        int len=0;

        for(int j=1;j<=n;j++)
        {

            if(!book[i][j]&&!book[j][i])//没有对决
            {
                if(shu[j])//还能再输
                {
                    if(len+1<=ying[i])
                    {
                        len++;

                        shu[j]--;

                        book[i][j]=1;

                        book[j][i]=1;



                        ans[i][j]=1;

                        ans[j][i]=-1;

                    }
                }
            }
        }


        for(int j=1;j<=n;j++)
        {
            if(!book[i][j]&&!book[j][i])
            {
                if(!ping[i]&&!ping[j])
                {
                    ping[i]=1;
                    ping[j]=1;
                    book[i][j]=1;

                    book[j][i]=1;

                    ans[i][j]=0;

                    ans[j][i]=0;

                }
            }
        }


    }
}
int main ()
{



int t;

cin>>t;

while(t--)
{


    cin>>n;


    if(n&1)
    work1((n-1)/2);
    else
    work2((n-2)/2);

    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            cout<<ans[i][j]<<" ";

        }
    }
    cout<<endl;



}

    return 0;

}