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

Minimum Ties - Luogu

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).

Because all teams have the same points , So the total score is kn, and n*(n-1)/2 The game , Therefore, a victory or defeat can be set x, It ends in a draw y

Pay attention to mathematical derivation , The division sign in practical problems must not be regarded as integral division ！！ The examination point of this question is whether to divide completely

3x+2y=kn

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

have to

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   // Propose fixed value n

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

The right side of the equation is an integer ,k The value of should let y Minimum

n If it's even   3(n-1)-2k  = 2t  (t=1,2,..)  

k =( 3(n-1)-2t  )/2     t=1 when k Maximum ,y Minimum  

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

n Is odd , obviously y=0

Then examine the construction techniques , Actually CFn^2 The class construction number filling problem routine is n^2 Direct scan construction , To ensure the correct answer , Just set more tag arrays , such as book[][] Represent whether to fight ,ping,sheng,shu Each represents the remaining draw , victory , Number of lost games , Strictly control

# 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)  // Each team wins cnt Time 
{

    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])// There is no duel 
            {
                if(shu[j])// Can you lose again 
                {
                    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])// There is no duel 
            {
                if(shu[j])// Can you lose again 
                {
                    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;

}