/* ACM Mid-Central Programming competition 2013 Problem B: Round Robin
solution by Andy Harrington
If anyone has an excess of turns, the person with the latest turn
must be one of them, so if only one person has an extra turn, it is the
one quitting, and everyone else has the same number, so we track the
number of players with one excess turn. Of course if every player
including the one about to quit has the same number of turns, we are also done.
It is unnecessary to process a single turn at a time: use division and
remainders. Alternate, turn by turn processing is shown in slowSolve
and the C++ solution.
*/
import java.util.*;
import java.io.*;
public class round
{
public static void main(String[] args) throws Exception {
String file = (args.length > 0) ? args[0] : "round.in";
Scanner in = new Scanner(new File(file));
int N = in.nextInt();
while (N != 0) {
solve(N, in.nextInt());
N = in.nextInt();
}
}
static void solve(int N, int T) {
judgeCheck(N, T); //judge testing
int minTurns = 0, // minimum turns for all player in game
excess = 0; // number of players with one more than the min.
while(true) {
minTurns += (excess + T) / N;
excess = (excess + T) % N;
N--; // person leaving
if (excess < 2) { //at most the person leaving has excess
System.out.println(N + " " + minTurns);
return;
}
excess--; // person leaving among those with the excess turn
}
}
// Done with quick solution: now an alternate to solve, one turn at a time
static void slowSolve(int N, int T) {
int[] turns = new int[N]; // count individual turns for all
int i = -1; // initialize so next turn at i+1
while(true) {
for (int j = 0; j < T; j++) { // add turn for T players
i = (i+1) % N ;
turns[i]++;
}
// i in position of last turn
for (int j = i; j < N-1; j++) // remove ith, shift
turns[j] = turns[j+1];
N--; // no longer use all of the array turns
if (allSame(turns, N)) {
System.out.println(N + " " + turns[0]);
return;
}
i--; // now next turn at i+1 again
}
}
static boolean allSame(int[] turns, int N) { // used by slowSolve
// true if turns[0] == turns[1] ==...==turns[N-1]
for (int i = 1; i < N; i++)
if (turns[0] != turns[i])
return false;
return true;
}
////////// rest for judges' testing ///////////
static int MAX_T = 100, MAX_N = 100; // judge problem limits
static void judgeCheck(int N, int T) {
if (N > MAX_N || T > MAX_T)
System.err.println("bad parameters");
}
}
|