OI题库

【问题描述】

FireDancer最近迷上了一个填数的游戏：一个n*n的正方形棋盘，要把从1到n^2的整数填入到这个棋盘的每一个格子里(随意)。玩了很多次后，FireDancer发现了很多有趣的性质，他现在想考考你。他希望你得到一种棋盘的填法，使得任意相邻的两个格子里的数相加的最大值最小。这里的相邻指的是四个方向上的有公共边的相邻，而不是八个方向上的相邻。

【输入文件】

一个整数n(2<=n<=50)。(30％的数据n<=10)

【输出文件】

一个整数，为最小的那个值。

【输入输出样例】

coupons.in
2

coupons.out
6
 

样例说明：
一种最优填数方案为
1 4
3 2
此时，所有相邻的格子中4+2的和最大，为6。
若按以下方法填数
1 3
2 4
则，4+3的和最大，为7，没有6来得优。