2014
02-14

# LCR

LCR is a simple game for three or more players. Each player starts with three chips and the object is to be the last person to have any chips. Starting with Player 1, each person rolls a set of three dice. Each die has six faces, one face with an L, one with a C, one with an R and three with a dot. For each L rolled, the player must pass a chip to the player on their left (Player 2 is considered to be to the left of Player 1); for each R rolled, the player passes a chip to the player on their right; and for each C rolled, the player puts a chip in a central pile which belongs to no player. No action is taken for any dot that is rolled. Play continues until only one player has any chips left. In addition, the following rules apply:

1. A player with no chips is not out of the game, since they may later gain chips based on other players’ rolls.
2. A player with only 1 or 2 chips left only rolls 1 or 2 dice, respectively. A player with no chips left does not roll but just passes the dice to the next player.

Your job is to simulate this game given a sequence of dice rolls.

Input will consist of multiple test cases. Each test case will consist of one line containing an integer n (indicating the number of players in the game) and a string (specifying the dice rolls). There will be at most 10 players in any game, and the string will consist only of the characters L’, C’, R’ and .’. In some test cases, there may be more dice rolls than are needed (i.e., some player wins the game before you use all the dice rolls). If there are not enough dice rolls left to complete a turn (for example, only two dice rolls are left for a player with 3 or more chips) then those dice rolls should be ignored. A value of n = 0 will indicate end of input.

Input will consist of multiple test cases. Each test case will consist of one line containing an integer n (indicating the number of players in the game) and a string (specifying the dice rolls). There will be at most 10 players in any game, and the string will consist only of the characters L’, C’, R’ and .’. In some test cases, there may be more dice rolls than are needed (i.e., some player wins the game before you use all the dice rolls). If there are not enough dice rolls left to complete a turn (for example, only two dice rolls are left for a player with 3 or more chips) then those dice rolls should be ignored. A value of n = 0 will indicate end of input.

3 LR.CCR.L.RLLLCLR.LL..R...CLR.
5 RL....C.L
0

Game 1:
Player 1:0
Player 2:0
Player 3:6(W)
Center:3

Game 2:
Player 1:1
Player 2:4
Player 3:1
Player 4:4(*)
Player 5:4
Center:1

//用STL里的priority_queue存储，剩下的就是模拟了。。
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <queue>
#define INF 0x7fffffff
using namespace std;

struct Process
{
int id;
int arr;    //到达时间
int last;
int prior;
};

struct cmp //按任务到达CPU的顺序进行存储
{
bool operator()(const Process &t1,const Process &t2)
{
if(t1.arr!=t2.arr)return t1.arr>t2.arr; //arr小的放在上面。小顶堆
return t1.prior<t2.prior;   //对于同时到达的，prior大的放在上面。大顶堆
}
};
struct cmp2//按任务执行的顺序存储
{
bool operator()(const Process &t1,const Process &t2)
{
if(t1.prior!=t2.prior)return t1.prior<t2.prior;
return t1.arr>t2.arr; //prior相同时，arr小的放在上面。即遵循first arrive,first serve

}
};
int main()
{
int num;
int cases=0;
while(cin>>num)
{
Process temp;
Process temp2;
if(cases!=0)printf("\n");
priority_queue<Process,vector<Process>,cmp> Q;   //所有待办任务的队列
priority_queue<Process,vector<Process>,cmp2> ing; //所有等待中的任务的队列,prior大的放上面
for(int i=0; i<num; i++)
{
cin>>temp.id>>temp.arr>>temp.last>>temp.prior;
Q.push(temp);
}
printf("CASE #%d\n",++cases);
int timer=0;
temp=Q.top();
Q.pop();

ing.push(temp); //第一个任务进入ing队
timer=temp.arr; //记录当前时间
while(1) //注意结束条件不能是Q为空。Q空了之后，还要再运行一次。
{
//temp=ing.top();
if(!Q.empty())
{
temp2=Q.top();
Q.pop();
}
else
{
temp2.arr=INF; //永远不会到来
temp2.last=0;
temp2.prior=0;
temp2.id=0;
}
bool flag=0;
while(!ing.empty())
{
temp=ing.top();
if(timer+temp.last<=temp2.arr)
{
timer+=temp.last;
printf("%d %d\n",temp.id,timer);
ing.pop();
}
else
{
flag=1;
break;
}
}
if(temp2.arr==INF)      //Q空了后，再循环一次，在这儿终止。
{
break;
}
if(flag)   //如果被打断
{
//   temp.arr=timer;
temp.last=temp.last-(temp2.arr-timer);//更新这个任务还需要的时间
timer=temp2.arr;
ing.pop();
ing.push(temp); //更新ing最上面那个
ing.push(temp2);
}
else if(!Q.empty())//没被打断，说明些时ing队列空了
{
timer=temp2.arr;
ing.push(temp2);
}
}

}
return 0;
}