/*
|
Problem description |
|
用边长小于N的正方形方砖（注意，不要求所有的方砖大小相同，请看样例说明）不重叠地铺满N*N的正方形房间，最少要几块方砖。 |
|
Input |
|
第一行是一个整数T,表示测试数据的组数,接下来的T 行，每一行是一个N(2<=N<=100) |
|
Output |
|
对于每一组测试数据输出一行，为最少需要的块数。 |
|
Sample Input |
2
4
5
|
|
Sample Output |
4
8
|
*/
#include <iostream>
using namespace std;
int GetNum(int m,int n)
{
int a=0;
if (n==0)
{
return 0;
}
a += m/n;
a += GetNum(n,m%n);
return a;
}
int main()
{
int T,N,temp,sum = 0,k=0;
//freopen("10086.txt","r",stdin);
cin>>T;
int *pRes = new int[T];
while (k<T)
{
cin>>N;
if (N%2==0)
{
pRes[k]=4;
k++;
continue;
}
if (N%3==0)
{
pRes[k]=6;
k++;
continue;
}
sum = N*N;
for (int i=N/2+1;i<N;i++)
{
temp = 0;
temp += GetNum(N,i);
temp += GetNum(N,N-i);
if (sum > temp)
sum = temp;
}
pRes[k]=sum;
k++;
}
for (int t=0;t<T;t++)
cout<<pRes[t]<<endl;
//fclose(stdin);
return 0;
}
#include <stdio.h>
#define MAX_N 100
int n;
int f[MAX_N+1][MAX_N+1];
int min( int a, int b )
{
if( a < b )
return a;
else
return b;
}
int CalF( int x, int y )
{
int res, k;
if( ( x == y ) && ( x < n ) )
return 1;
else {
res = 100000;
for( k = ( x / 2 ); k < x; k++ )
res = min( res, f[k][y] + f[x-k][y] );
return res;
}
}
void work()
{
int x, y;
for( x = 1; x <= n; x++ )
for( y = 1; y <= n; y++ ) {
f[x][y] = CalF(x,y);
f[y][x] = f[x][y];
}
}
void main()
{
for( n = 2; n <= MAX_N; n++ ) {
work();
printf("%5d %5d/n",n,f[n][n]);
}
}