小白月赛 F.草方块与牛排(构造)

小白月赛 F.草方块与牛排(构造)

小白月赛 F.草方块与牛排(构造)

显然 r = n 2 − 4 4 = n 2 4 − 1 r=dfrac{n^2-4}{4}=dfrac{n^2}{4}-1 r=4n2−4​=4n2​−1

使用的个数 r r r为整数， n n n必须为偶数。

将行按照奇偶染色(第一行染0，第二行染1…)。那么牛排的类型只能为3个1、1个0 或者是3个0，1个1。

因为0和1的个数相等。

3 x + y = 3 y + x 3x+y=3y+x 3x+y=3y+x，所以 x = y x=y x=y。

r = 2 x r=2x r=2x， r r r为偶数。

假设 n = 4 k n=4k n=4k，那么 r = 4 k 2 − 1 r=4k^2-1 r=4k2−1为奇数，矛盾。

因此 n = 4 k + 2 n=4k+2 n=4k+2型。

// Problem: 草方块与牛排
// Contest: NowCoder
// URL: 
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor ()#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-(x)))
#define lg2(x) ((int)(__lg(x)/__lg(2)))
typedef long long LL;
typedef unsigned long long ull;
const int N=1e6+10,INF=2e9+10;
inline int read(){int ret=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){ if(ch=='-') f=-f; ch=getchar(); }while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();return ret*f;
}
inline void write(int x){        if(x<0){ putchar('-'); x=-x; }      if(x>9) write(x/10);     putchar(x%10+'0');     
}
int n;
inline int get(int x,int y){return (x-1)*n+y;
}
void print1(int x,int y){write(get(x,y)),putchar(' ');write(get(x,y+1)),putchar(' ');write(get(x,y+2)),putchar(' ');write(get(x+1,y)),putchar('n');write(get(x+1,y+3)),putchar(' ');write(get(x+1,y+2)),putchar(' ');write(get(x+1,y+1)),putchar(' ');write(get(x,y+3)),putchar('n');
}
void print2(int x,int y){write(get(x,y)),putchar(' ');write(get(x+1,y)),putchar(' ');write(get(x+2,y)),putchar(' ');write(get(x,y+1)),putchar('n');write(get(x+3,y+1)),putchar(' ');write(get(x+2,y+1)),putchar(' ');write(get(x+1,y+1)),putchar(' ');write(get(x+3,y)),putchar('n');
}
int main(){n=read();if(n%4==2){write((n*n-4)/4),putchar('n');for(int j=3;j<=n;j+=4)for(int i=1;i<=n;i+=2)print1(i,j);for(int i=3;i<=n;i+=4) print2(i,1);}else write(-1);return 0;
}