/*******************************************************************************
* Name: Kevin Wayne
* Login: wayne
* Precept: P00
*
* Compilation: javac HuntingtonHill.java
* Execution: java HuntingtonHill H < input.txt
* Dependencies: StdIn.java StdOut.java
*
* Reads an integer H from the command line, an integer N and N pairs of
* names and populations from standard input; writes the Huntington-Hill
* apportionment to standard output.
*
******************************************************************************/
public class HuntingtonHill {
public static double priority(int population, int seat) {
return population / Math.sqrt(1.0*seat * (seat+1));
}
public static int next(int[] populations, int[] seats) {
int max = 0;
for (int i = 0; i < populations.length; i++) {
if (priority(populations[i], seats[i]) > priority(populations[max], seats[max]))
max = i;
}
return max;
}
public static void main(String[] args) {
int H = Integer.parseInt(args[0]);
// read in populations of each state
int N = StdIn.readInt();
String[] names = new String[N];
int[] populations = new int[N];
for (int i = 0; i < N; i++) {
names[i] = StdIn.readString();
populations[i] = StdIn.readInt();
}
// initialize 1 seat per state
int[] seats = new int[N];
for (int i = 0; i < N; i++)
seats[i] = 1;
// Huntington-Hill algorithm
for (int i = 0; i < H - N; i++) {
int max = next(populations, seats);
seats[max]++;
}
// print results
for (int i = 0; i < N; i++) {
StdOut.printf("%-16s %8d %5d\n", names[i], populations[i], seats[i]);
}
}
}