学步园

题目描述：

109. Magic of David Copperfield II

time limit per test: 0.5 sec.

memory limit per test: 4096 KB

The well-known magician David Copperfield loves lo show the following trick: a square with N rows and N columns of different pictures appears on a TV screen, Let us number all the
pictures in the following order:

Each member of the audience is asked to put a finger on the upper left picture (i.e., picture number one) and The Magic begins: the magician tells the audience to move the finger K₁ times through the pictures (each move is a shift of the finger to
the adjacent picture up, down, left or right provided that there is a picture to move to), then with a slight movement of his hand he removes some of the pictures with an exclamation "You are not there!", and ... it is true - your finger is not pointing to
any of the pictures removed. Then again, he tells the audience to make K₂ moves, and so on. At the end he removes all the pictures but one and smiling triumphantly declares, "I've caught you" (applause).

Just now, David is trying to repeat this trick. Unfortunately, he had-a hard day before, and you know how hard to conjure with a headache. You have to write a program that will help David to make his trick.

Input

The input file contains a single integer number N (1<N<101).

Output

Your program should write the following lines with numbers to the output file:
K₁ X_1,1 X_1,2 ... X_1,m1
K₂ X_2,1 X_2,2 ... X_2,m2
...
K_e X_e,1 X_e,2 ... X_e,me
where K_i is a number of moves the audience should make on the i-th turn (N<=K_i<300). All Ki, should be different (i.e. K_i<>K_j when i<>j). X_i,1 X_i,2 ... X_i,mi are the numbers of the
pictures David should remove after the audience will make K_i moves (the number of the pictures removed is arbitrary, but each picture should be listed only once, and at least one picture should be removed on each turn).
A description of the every next turn should begin with a new line. All numbers on each line should be separated by one or more spaces. After e iterations, all pictures except one should be removed.

Sample Input

3

Sample Output

3 1 3 7 9
5 2 4 6 8

个人感觉比较恶心的构造，主要是本弱菜不会实现，代码写的很挫。。。

很显然就是黑白染色然后每次走奇数步保证我们可以放心地对某些数据进行操作。

然后我们观察一下n=2*k+1 就是n为奇数的方法。

用上图的方法就能将 n=2*k+1 问题转化成求解2*(k-1)+1的子问题。

那么如果n=2*k ，又将如何是好，经研究，我们可以将其转化成奇数，具体操作见下图：

那么我们就可以成功搞定这个题，具体 的实现对于我这样的若菜还是有一定难度的。

但是好不容易A了，贴个代码，仅供参考：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#include<algorithm>
#include<vector>
#include<cstdlib>

#define inf 0xfffffff
#define CLR(a,b) memset((a),(b),sizeof((a)))

using namespace std;
int const nMax = 110;
int const base = 10;
typedef int LL;
typedef pair<LL,LL> pij;

int map[nMax][nMax];
int n,k;

void cut(){
    printf("%d",k);k+=2;
    for(int i=2;i<n;i+=2)printf(" %d",map[i][n]);
    for(int j=2;j<n;j+=2)printf(" %d",map[n][j]);
    printf( " %d\n",map[n][n]);
    printf("%d",k);k+=2;
    for(int j=1;j<=n;j+=2)printf(" %d",map[n][j]);
    for(int i=1;i<=n;i+=2)printf(" %d",map[i][n]);
    printf("\n");
    n--;
    return ;
}

void work(){
    int nx=1,ny=1;
    while(nx!=n/2+1){
    printf("%d",k);k+=2;
    for(int j=ny;j<=n-ny+1;j+=2)printf(" %d %d",map[n-nx+1][j],map[nx][j]);
    for(int i=nx+2;i<n-nx+1;i+=2)printf(" %d %d",map[i][n-ny+1],map[i][ny]);
    printf("\n");
    printf("%d",k);k+=2;
    for(int j=ny+1;j<=n-ny+1;j+=2)printf(" %d %d",map[n-nx+1][j],map[nx][j]);
    for(int i=nx+1;i<n-nx+1;i+=2)printf(" %d %d",map[i][n-ny+1],map[i][ny]);
    printf("\n");
    nx++;
    ny++;
    }
}

int main(){
    cin>>n;
    int l=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            map[i][j]=l++;
        }
    }
    k=n;
    if(k%2==0)k++;
    if(n%2==0)cut();
    work();
    return 0;
}