POJ 1879

栈和队列的综合应用，利用栈和队列分别模拟分，5分，时槽，以及小球队列

利用求出一天后的置换可以求出周期，进而求出最大公约数（可以利用矩阵的角度，也许可以简化，因为每次都是乘上一个相同的置换矩阵）

要注意读题，时槽满12归队的方式很不一样

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <stack>

#include <queue>

using namespace std;

const int maxn= 127+5;

const int dms= 24*60;

int T[maxn], chg[maxn];

stack<int> h, fvm, m;

queue<int> bl;

int ans;

int Gcd(int a, int b)

{

	return 0== b? a : Gcd(b, a%b);

}

void Init(int n)

{

	ans= 1;

	while (!bl.empty()){

		bl.pop();

	}

	while (!h.empty()){

		h.pop();

	}

	while (!fvm.empty()){

		fvm.pop();

	}

	while (!m.empty()){

		m.pop();

	}

	for (int i= 0; i< n; ++i){

		T[i]= 1;

	}

	for (int i= 0; i< n; ++i){

		bl.push(i);

	}

}

int main()

{

	int n;

	while (1){

		scanf("%d", &n);

		if (0== n){

			break;

		}

		Init(n);

		for (int i= 0; i< dms; ++i){

			int obl= bl.front();

			bl.pop();

			if (4== m.size()){

				for (int j= 0; j< 4; ++j){

					bl.push(m.top());

					m.pop();

				}

				if (11== fvm.size()){

					for (int j= 0; j< 11; ++j){

						bl.push(fvm.top());

						fvm.pop();

					}

					if (11== h.size()){

						for (int j= 0; j< 11; ++j){

							bl.push(h.top());

							h.pop();

						}

						bl.push(obl);

					}else{

						h.push(obl);

					}

				}

				else{

					fvm.push(obl);

				}

			}

			else{

				m.push(obl);

			}

		}

		for (int i= 0; i< n; ++i){

			chg[i]= bl.front();

			// cout<<i<<" "<<chg[i]<<endl;

			bl.pop();

		}

		for (int i= 0; i< n; ++i){

			int ni= chg[i];

			while (ni!= i){

				ni= chg[ni];

				++T[i];

			}

		}

		for (int i= 0; i< n; ++i){

			ans= ans*T[i]/Gcd(ans, T[i]);

		}

		cout << n << " balls cycle after "<< ans<<" days."<<endl;

	}

	return 0;

}

巴特西

POJ 1879

最新文章

热门文章