gistfile1.java

package com.topcoder;

public class Bonuses {

	public int[] getDivision(int[] points) {
		
		int bonuses[] = new int[points.length];
		int pool = 0, percentsLeft = 100;
		
		for (int point : points) {
			pool += point;
		}
		
		for (int i = 0; i < points.length; i++) {
			bonuses[i] = (int)(points[i] / (float)pool * 100);
			percentsLeft -= bonuses[i];
		}
		
		int[] sorted = new int[bonuses.length];
		int[] tmp = new int[bonuses.length];
		for (int i = 0; i < bonuses.length; i++) {
			sorted[i] = i;
			tmp[i] = bonuses[i];
		}
		
		for (int i = 0, min = 0; i < tmp.length - 1; i++) {
			min = i;
			for (int j = i + 1; j < tmp.length; j++) {
				if (tmp[j] >= tmp[min]) {
					min = j;
				}
			}
			int k = tmp[i];
			tmp[i] = tmp[min];
			tmp[min] = k;
			k = sorted[i];
			sorted[i] = sorted[min];
			sorted[min] = k;
		}
		
		for (int i = 1, v = 0, c = 0; i < sorted.length;) {
			v = bonuses[sorted[i]];
			while(i < sorted.length && v == bonuses[sorted[i]]) {
				for (int j = i; j > c; j--) {
					if (sorted[j] < sorted[j - 1]) {
						int k = sorted[j];
						sorted[j] = sorted[j - 1];
						sorted[j - 1] = k;
					}
				} 
				i++;
			}
			c = i;
		}
		
		for (int i = 0; i < percentsLeft; i++) {
			bonuses[sorted[i]]++;
		}
		
		return bonuses;
		
	}
	
	public static void main(String[] args) {
		
		Bonuses b = new Bonuses();
		int[] result = b.getDivision(new int[]{485, 324, 263, 143, 470, 292, 304, 188, 100, 254, 296, 255, 360, 231, 311, 275,  93, 463, 115, 366, 197, 470});
		
		for (int i = 0; i < result.length; i++) {
			System.out.print(result[i] + ",  ");
		}
		
	}

}