2014
01-05

# Containers

At a container terminal, containers arrive from the hinterland, one by one, by rail, by road, or by small ships. The containers are piled up as they arrive. Then the huge cargo ships arrive, each one capable of carrying thousands of containers. The containers are loaded into the ships that will bring them to far away shores. Or the other way round, containers are brought in over sea, piled up, and transported to the hinterland one by one. Anyway, a huge parking lot is needed, to store the containers waiting for further transportation.

Building the new container terminal at the mouth of the river was a good choice. But there are disadvantages as well. The ground is very muddy, and building on firm ground would have been substantially cheaper. It will be important to build the parking lot not larger than necessary.

A container is 40 feet long and 8 feet wide. Containers are stacked, but a stack will be at most five containers high. The stacks are organized in rows. Next to a container stack, and between two container stacks (along the long side of the containers) a space of 2 feet is needed for catching the containers. Next to a row of stacks, and between two stacks (along the short side of the containers) a space of 4 feet is needed for the crane that lifts the containers. All containers are placed in the same direction, as the cranes can not make turns on the parking lot.

The parking lot should be rectangular. Given the required capacity of the parking lot, what will be the best dimension for the parking lot? In the first place the area should be minimal. The second condition is that the parking lot should be as square as possible.

Below you see a plan for a parking lot with a capacity of 8 stacks. Two rows of four containers each turns out to be the best solution here, with a total area of 92 × 42 = 3864.

A parking lot with 8 container stacks.

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

A single positive integer n (n ≤ 1012) on a single line: the required capacity (number of containers) for the parking lot.

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

A single positive integer n (n ≤ 1012) on a single line: the required capacity (number of containers) for the parking lot.

6
1
15
22
29
36
43

48 X 12 = 576
48 X 32 = 1536
52 X 48 = 2496
92 X 32 = 2944
92 X 42 = 3864
136 X 32 = 4352

“在理想情况下，能用常量时间查找到指定值的数据”。

=====================分割线=======================

POJ3349就是利用哈希这个特点的一个典型应用。题目本身与存取无关，而只是要找出是否有数据出现过一次以上。就可以采取上述“标记”+“映射”的方法。

CODE:

/*hash判重*/
/*
1. 直接相加, 把(总和%大质数)为key.
2. 平方和相加, 把(总和%大质数)为key.
3. 从小到大的顺序, 对v[i]<<(i*3)依次异或, 然后模一个大质数作为key.(by hust07p43)
4. 六个数中非零数的积再乘上一个大质数,然后模一个100w上下的数。

5. 依次对每个数异或所得的数作为key. (by archerstarlee)
6. (a[0] + a[2] + a[4])&(a[1] + a[3] + a[5]), 再模一个大质数. 中间的&还可以改成'|' 或者'^'.非常巧妙! 我采用'^'得到最快的719ms. (只对本题适用的hash方法)

*/
/*AC代码：2344ms*/
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <cstdlib>
#define MAXN 100000
#define MOD 99991
using namespace std;
struct Node
{
int val[7];
};
struct Node Hash[MAXN][20];//hash表
int len[MAXN];//相应hash表的长度
int N;
bool ok;
int hash(Node u)//hash函数
{
int i,sum=0;
for(i=1;i<=6;i++)
sum+=u.val[i];
return sum%MOD;
}
void Rotate(Node &u)//移动
{
int i,t=u.val[1];
for(i=1;i<=5;i++)
u.val[i]=u.val[i+1];
u.val[6]=t;
}
void Reverse(Node &u)//翻转
{
Node v;
int i,j;
for(i=1,j=6;i<=6;i++,j--)
v.val[i]=u.val[j];
u=v;
}
bool Equal(Node u,Node v)//判断是否相等
{
int i;
for(i=1;i<=6;i++)
{
if(u.val[i]!=v.val[i])
return false;
}
return true;
}
void Judge(Node u,Node v)
{
int i;
for(i=1;i<=6;i++)
{
Rotate(u);
if(Equal(u,v)) {ok=false;return;}
}
Reverse(u);
for(i=1;i<=6;i++)
{
Rotate(u);
if(Equal(u,v)) {ok=false;return;}
}
}
void Init()
{
int i,j;
Node u;
ok=true;
memset(len,0,sizeof(len));
for(i=1;i<=N;i++)
{
for(j=1;j<=6;j++)
scanf("%d",&u.val[j]);
if(!ok) continue;
int pos=hash(u);
for(j=0;j<len[pos];j++)
{
Judge(u,Hash[pos][j]);
if(!ok) break;
}
Hash[pos][len[pos]++]=u;
}
}
void Solve()
{
if(ok) printf("No two snowflakes are alike.\n");
else printf("Twin snowflakes found.\n");
}
int main()
{
while(scanf("%d",&N)!=EOF)
{
Init();
Solve();
}
return 0;
}

1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

2. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1