Round Robin | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:65536KB |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Total submit users: 37, Accepted users: 30 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Problem 12940 : No special judgement | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Problem description | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Suppose that N players sit in order and take turns in a game, with the first person following the last person, to continue in cyclic order. While doing so, each player keeps track of the number of turns he or she has taken. The game consists of rounds, and As an example, assume we begin a game with N=5 and T=17, labeling the players in order as A, B, C, D, and E, with all counts initially zero.
Beginning with A, 17 turns are taken. B will have taken the last of those turn, leaving our counts as follows:
Suppose that after every 17 turns, the player who just had a turn is eliminated from the game. All remaining players then compare their counts. If all of those counts are equal, everyone has had a fair number of turns Continuing with our example, B will leave the game, and the next turn will be for C.
After 17 more turns starting with C, we find that A, D and E received 4 turns, while C received 5 turns, including the last:
Then C leaves, and since the remaining counts are not all the same, a new round beings with D having the next turn.
The next 17 turns start with D and end with E. A adds 5 turns, while D and E add 6:
Then E leaves.
At this point, notice that the two remaining players have the same count of 13. Therefore, the game ends. (We note that E's count was irrelevant to the decision to end the game.) |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Input | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
The input will contain one or more datasets. Each dataset will be described with a single line containing two integers, |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Output | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
There is one line of output for each dataset, containing two numbers, |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Sample Input | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5 17 7 10 90 2 0 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Sample Output | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2 13 5 3 45 1 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Problem Source | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ACM Mid-Central Programming Competition 2013
#include<stdio.h> typedef struct nnnn { int count; struct nnnn *next; }node; int MAX(int a,int b){return a>b?a:b;} int MIN(int a,int b){return a<b?a:b;} node *head; void builde(int n) { node *p; head=new node; head->count=0; head->next=head; for(int i=2;i<=n;i++) { p=new node; p->count=0; p->next=head->next; head->next=p; } } void find(int t,int n) { int max=0,min=9999999; while(max!=min) { int i=1; head->count++; if(t==1) { while(i<n) head=head->next; } else while(i<t-1) { i++; head=head->next; head->count++; } head->next=(head->next)->next; n--; max=0,min=9999999; for(i=1;i<=n+1;i++) { if(max<(head->count))max=head->count; if(min>(head->count))min=head->count; head=head->next; } } printf("%d %d\n",n,max); } int main() { int n,t,st; while(scanf("%d",&n)>0&&n) { scanf("%d",&t); builde(n); find(t,n); } } |