1256 : 方砖问题

时间限制:1 Sec 内存限制:128 MiB
提交:56 答案正确:39

提交 状态 讨论区

题目描述

用边长小于N的正方形方砖(注意,不要求所有的方砖大小相同,请看样例说明)不重叠地铺满N*N的正方形房间,最少要几块方砖。

输入

第一行是一个整数T,表示测试数据的组数,接下来的T 行,每一行是一个N(2<=N<=100)

输出

对于每一组测试数据输出一行,为最少需要的块数。

样例输入

复制
2 
4 
5

样例输出

复制
4 
8

提示

当N=4时 
最优的铺砖方法 
AABB 
AABB 
CCDD 
CCDD 
A,B,C,D为四块方砖的代号。 
其他的铺砖方法,例如: 
AAAB 
AAAC 
AAAD 
EFGH 
需要的8块方砖,不是最少的。

来源