LightOj1303

As we all know that not only children but Ferris-Wheel (FW) is favorite to all ages. That's why the LightOJ Park has made a special FW for the programmers. And unlike other Ferris-Wheels, this FW has m seats and every seat is different and very special. Since its circular, the seats are numbered from 1 to m in anticlockwise order, so seat 2 is adjacent to seat 1 and seat 3, seat 1 is adjacent to seat 2 and seat m.
One day n programmers (identified by 1 to n) came and each of them wanted to ride in the FW. Since every seat is special, everyone wants to taste the ride of every seat. So, they made the following algorithm:
1.      They will form a queue from 1 (front) to n (back). As they want to enjoy the ride, they want to sit alone in a seat, because two (or more) may start problem-solving in the ride.
2.      The FW moves in clockwise order. Initially the seat 1 is in bottom and after 5 seconds, it starts. And when it starts, in each 5 second interval the next seat comes to bottom. So, the order of the seats in bottom are seat 1 (at time 5), seat 2 (at time 10), ..., seat m (at time 5*m), seat 1 (at time 5*m+5), ... and in this interval, a person sits in that seat or gets out (if he is in the seat) or both (one gets out and another gets in). Assume that these kinds of movements take quite a small time and thus that can be ignored.
3.      When a programmer gets out from one seat (he just rode in that seat), then if he has ridden in all the seats, he will leave, otherwise he will join in the back of the queue.
4.      When a seat comes into bottom, if all the programmers in the queue have ridden in the seat, nothing happens. Otherwise the first person (from front) in the queue who hasn't ridden in the seat sits in that seat and other programmers keep standing. For example, the current queue is 5, 2, 3, 1 and a seat is in the bottom which has been already ridden by 5 and 2 but 3 hasn't; so, 3 will sit in that seat leaving the queue: 5, 2, 1.
Now you are the (n+1)th programmer and you are unlucky, because you are assigned a task, and the task is to find the minimum time when you are sure that everyone has ridden in all the seats.
Input
Input starts with an integer T (≤ 400), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 20) and m (2 ≤ m ≤ 20).
Output
For each case, print the case number and the time.
Sample Input
Output for Sample Input
2 2 3 3 2
Case 1: 65 Case 2: 40
テーマ:
n人のプログラマーは観覧車の各席に座るつもりで、席が底にあるときだけ降りることができて、列の最後に並んで、あるいは列の中で最初にこの席に座ったことがない人が座ることができます.プログラマーは同じ席を繰り返してはいけません.
観覧車が次の席に移動するたびに5分かかります.少なくともどのくらいですべてのプログラマーがすべての席に座ることができますか.
この問題は直接シミュレーションして、プログラミング能力を訓練します.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct Man
{
	vector<int>vis;
};
struct Seat
{
	int num;
	int people;
	bool Empty;
};
int n, m;
int getTime()
{
	queue<Seat>wl;
	Man man[21];
	vector<int>wait;
	for (int i = 1; i <= m; ++i)
	{
		Seat a;
		a.Empty = true;
		a.num = i;
		a.people = -1;
		wl.push(a);
	}
	for (int i = 1; i <= n; ++i)
	{
		wait.push_back(i);
	}
	int USETIME = 0;
	for (USETIME = 1;; USETIME += 1)
	{
		Seat sit = wl.front();
		wl.pop();
		int s = sit.num;
		if (!sit.Empty)
		{
			wait.push_back(sit.people);
			man[sit.people].vis.push_back(sit.num);
		}
		int j;
		for (j = 0; j<wait.size(); ++j)
		{
			bool si = true;
			for (int p = 0; p<man[wait[j]].vis.size(); ++p)
			{
				if (man[wait[j]].vis[p] == s)
				{
					si = false;
					break;
				}
			}
			if (si)
				break;
		}
		if (j != wait.size())
		{
			Seat sea;
			sea.Empty = false;
			sea.num = s;
			sea.people = wait[j];
			wait.erase(wait.begin() + j);
			wl.push(sea);
		}
		else
		{
			Seat se;
			se.Empty = true;
			se.num = s;
			wl.push(se);
		}
		bool leave = true;
		for (int i = 1; i <= n; ++i)
		{
			if (man[i].vis.size() != m)
			{
				leave = false;
				break;
			}
		}
		if (leave)
			break;
	}
	return USETIME;
}
int main()
{
	int cou = 0;
	int Time;
	cin >> Time;
	while (Time--)
	{
		cin >> n >> m;
		cout<<"Case "<<++cou<<": "<< 5 * getTime() << endl;
	}
}

この問題のもっと簡単な方法は、1つの2次元配列で人(1次元は人の番号を表し、もう1次元は席の番号を表す)をシミュレートし、ある位置に座って1を記入し、座ったことがなく0を記入することです.
次いで、観覧車を1次元配列で表し、int i=0である.for(;;i=(i+1)%m)はループを表し,queueを用いずにコードの難易度を簡素化し,効率を向上させることができる.