染色问题

染色问题

基准时间限制：1 秒 空间限制：10240 KB 分值: 40

一个n(3<=n<=100)个点的完全图，现在给出n，要求将每条边都染上一种颜色k(1<=k<=n)，最终使得所有三个点构成的环（C(n,3)个不同的换）上三条边的颜色和在所有颜色中任选三种颜色的组合（C(n,3)种方案）一一对应，由你来给出染色方案。

本题有多组数据

Input

第一行一个整数T，表示数据组数
接下来T行每行一个整数n，表示完全图的点数

Output

输出由T个部分组成
每个部分的第一行一个整数n，表示完全图的点数
第二行表示构造结果
如果无解输出No solution
否则输出n*(n-1)/2条边的起点、终点和颜色

Input示例

2
4
3

Output示例

4
No solution
3
1 2 3 2 3 1 3 1 2
首先可以证明当n为偶数的时候是无解的。

根据轮换对称性，每种颜色的边应该数量相同，即C(n,2)/n=(n-1)/2，当n为偶数的时候这个值不是整数。

所以当且仅当n为奇数时本题有解。

那么接下来可以找到一种构造方案，使解满足题意：

把这个完全图画在平面上，就是一个正n边形，现在这个C(n,2)条边中所有平行的边染同一种颜色，那么就可以满足题意。

即(i,j)之间的边颜色是(i+j)%n+1。

下面来证明这个构造方案是合法的。

假设这样染色是不合法的，即有两个三角形不完全相同但三边颜色相同。

那么这两个三角形的三边一定是互相平行的。

又因为这两个三角形的顶点都在正n边形的外接圆上。

所以这两个三角形共外接圆，即这两个三角形全等。

既然这两个三角形全等，那么只有两种情况，要么重合要么中心对称。

然而这两个三角形的顶点是一个圆的奇数等分点，所以不可能中心对称。

因此这两个三角形重合，而这与假设中的不完全相同矛盾。

即这种构造方案是合法的。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<queue>
#include<stack>
#include<math.h>
using namespace std;
typedef long long LL;
int main(void)
{
        int T;
        scanf("%d",&T);
        while(T--)
        {
                int n;
                scanf("%d",&n);
                if(n%2==0)
                {      printf("%dn",n);
                        printf("No solutionn");
                }
                else
                {       int flag = 0;printf("%dn",n);
                        for(int i = 1; i <= n; i++)
                        {
                                for(int j = i+1; j <= n; j++)
                                {
                                    if(!flag)
                                    {
                                        printf("%d %d %d",i,j,(i+j)%n+1);
                                        flag = 1;
                                    }
                                    else printf(" %d %d %d",i,j,(i+j)%n+1);
                                }
                        }
                }
                printf("n");
        }
        return 0;
}