C. Labs

outputstandard output

In order to do some research, n2n2 labs are built on different heights of a mountain. Let’s enumerate them with integers from 11 to n2n2, such that the lab with the number 11 is at the lowest place, the lab with the number 22 is at the second-lowest place, ……, the lab with the number n2n2 is at the highest place.

To transport water between the labs, pipes are built between every pair of labs. A pipe can transport at most one unit of water at a time from the lab with the number uu to the lab with the number vv if u>vu>v.

Now the labs need to be divided into nn groups, each group should contain exactly nn labs. The labs from different groups can transport water to each other. The sum of units of water that can be sent from a group AA to a group BB is equal to the number of pairs of labs (u,vu,v) such that the lab with the number uu is from the group AA, the lab with the number vv is from the group BB and u>vu>v. Let’s denote this value as f(A,B)f(A,B) (i.e. f(A,B)f(A,B) is the sum of units of water that can be sent from a group AA to a group BB).

For example, if n=3n=3 and there are 33 groups XX, YY and ZZ: X={1,5,6},Y={2,4,9}X={1,5,6},Y={2,4,9} and Z={3,7,8}Z={3,7,8}. In this case, the values of ff are equal to:

• f(X,Y)=4f(X,Y)=4 because of 5→25→2, 5→45→4, 6→26→2, 6→46→4,
• f(X,Z)=2f(X,Z)=2 because of 5→35→3, 6→36→3,
• f(Y,X)=5f(Y,X)=5 because of 2→12→1, 4→14→1, 9→19→1, 9→59→5, 9→69→6,
• f(Y,Z)=4f(Y,Z)=4 because of 4→34→3, 9→39→3, 9→79→7, 9→89→8,
• f(Z,X)=7f(Z,X)=7 because of 3→13→1, 7→17→1, 7→57→5, 7→67→6, 8→18→1, 8→58→5, 8→68→6,
• f(Z,Y)=5f(Z,Y)=5 because of 3→23→2, 7→27→2, 7→47→4, 8→28→2, 8→48→4.

Please, divide labs into nn groups with size nn, such that the value minf(A,B)minf(A,B) over all possible pairs of groups AA and BB (A≠BA≠B) is maximal.

In other words, divide labs into nn groups with size nn, such that minimum number of the sum of units of water that can be transported from a group AA to a group BB for every pair of different groups AA and BB (A≠BA≠B) as big as possible.

Note, that the example above doesn’t demonstrate an optimal division, but it demonstrates how to calculate the values ff for some division.

If there are many optimal divisions, you can find any.Input

The only line contains one number nn (2≤n≤3002≤n≤300).Output

Output nn lines:

In the ii-th line print nn numbers, the numbers of labs of the ii-th group, in any order you want.

If there are multiple answers, that maximize the minimum number of the sum of units of water that can be transported from one group the another, you can print any.ExampleinputCopy

3

outputCopy

2 8 5
9 3 4
7 6 1

Note

In the first test we can divide 99 labs into groups {2,8,5},{9,3,4},{7,6,1}{2,8,5},{9,3,4},{7,6,1}.

From the first group to the second group we can transport 44 units of water (8→3,8→4,5→3,5→48→3,8→4,5→3,5→4).

From the first group to the third group we can transport 55 units of water (2→1,8→7,8→6,8→1,5→12→1,8→7,8→6,8→1,5→1).

From the second group to the first group we can transport 55 units of water (9→2,9→8,9→5,3→2,4→29→2,9→8,9→5,3→2,4→2).

From the second group to the third group we can transport 55 units of water (9→7,9→6,9→1,3→1,4→19→7,9→6,9→1,3→1,4→1).

From the third group to the first group we can transport 44 units of water (7→2,7→5,6→2,6→57→2,7→5,6→2,6→5).

From the third group to the second group we can transport 44 units of water (7→3,7→4,6→3,6→47→3,7→4,6→3,6→4).

The minimal number of the sum of units of water, that can be transported from one group to another is equal to 44. It can be proved, that it is impossible to make a better division.

---

思路：其实把样例给的数据按顺序写下发现是先竖着走到底再往右拐弯上去再往右下来。

原因：从样例开始构造，构造的时候要保证相邻的慢慢拉平，第一列构造完了，第二列的开头为了保证拉回来，放最小的大于下面序列的数，也就是多出个2.这一列的下面两个序列再降序。这样扩展下去能保证最小。画完发现就是个走迷宫的样子。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=400;
typedef long long LL;
LL a[maxn][maxn];
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL n;cin>>n;
  LL cnt=0;
  for(LL j=1;j<=n;j++)
  {
  	 if(j%2==1)
  	 {
  	 	for(LL i=1;i<=n;i++)
  	 	 	a[i][j]=++cnt;
	 }
	 else if(j%2==0)
	 {
	 	for(LL i=n;i>=1;i--)
	 		a[i][j]=++cnt;
	 }
  }
  for(LL i=1;i<=n;i++)
  	{
  		for(LL j=1;j<n;j++)
		  	cout<<a[i][j]<<" ";
		cout<<a[i][n]<<endl;	  	
	}
return 0;
}