201011 - 小球钟

#include <bits/stdc++.h>
using namespace std;

const int Limit[4]={5,3,4,24}; //定义每一行轨道可以容纳的小球个数
int Line[4][25]; //四行轨道，即一分，五分，15分，一个小时的运行轨道
int solved[300]; //保存1
deque Q; //定义队列 （不会的看第一册书）

int GCD(int m,int n) {

return n==0?m:GCD(n,m%n); //求最大公约数 
}

long long GetDay(int n) {

int j,k;
long long ans=1;
for(int i=0;i<n;++i) //枚举每一个小球 
{
	for(j=Q[i],k=1;j!=i;j=Q[j],++k); //计算周期k 
	ans=ans*k/GCD(ans,k); //求此之前小球与之前所有小球的周期的最小公倍 
}
return ans;
}

int Solve(int n) {

Q.clear(); //不用说你也知道干嘛的 
for(int i=0;i<n;++i) //初始化 
	Q.push_back(i);
while(1)
{
	Line[0][++Line[0][0]]=Q.front(); //记录第i行轨道的已有球数 
	Q.pop_front();
	for(int i=0;i<3;++i) //枚举1,5,15分钟 
		if(Line[i][0]==Limit[i]) //若达到极限 
		{
			Line[i+1][++Line[i+1][0]]=Line[i][Line[i][0]--]; //最后一刻球滚入下行 
			while(Line[i][0]!=0)
				Q.push_back(Line[i][Line[i][0]--]); //剩余的球依次进入队列 
		}
		if(Line[3][0]==Limit[3]) //24小时！？ 
		{
			int o=Line[3][0]--; //记录 
			while(Line[3][0]!=0) //其他球依次进入 
				Q.push_back(Line[3][Line[3][0]--]);
			Q.push_back(Line[3][o]); //让他进去 
			break;
		}
}
return GetDay(n);
}

int main() {

int n;
while(cin>>n,n!=0)
	if(solved[n]!=0)
		cout<<solved[n]<<'\n'; //计算过，还算来干嘛？ 
	else
		cout<<(solved[n]=Solve(n))<<'\n'; //输出 
return 0;
}