1535d63cea 2011-05-28        kinaba: import java.math.*;
1535d63cea 2011-05-28        kinaba: import java.util.*;
1535d63cea 2011-05-28        kinaba: 
1535d63cea 2011-05-28        kinaba: public class TheJackpotDivOne {
1535d63cea 2011-05-28        kinaba: 	public long[] find(long[] money, long jackpot)
1535d63cea 2011-05-28        kinaba: 	{
1535d63cea 2011-05-28        kinaba: 		long M = 0;
1535d63cea 2011-05-28        kinaba: 		for(int i=0; i<money.length; ++i)
1535d63cea 2011-05-28        kinaba: 			if( M < money[i] )
1535d63cea 2011-05-28        kinaba: 				M = money[i];
1535d63cea 2011-05-28        kinaba: 
1535d63cea 2011-05-28        kinaba: 		boolean unsat_case = false;
1535d63cea 2011-05-28        kinaba: 		{
1535d63cea 2011-05-28        kinaba: 			long J = jackpot;
1535d63cea 2011-05-28        kinaba: 			for(int i=0; i<money.length; ++i) {
1535d63cea 2011-05-28        kinaba: 				J -= M-money[i];
1535d63cea 2011-05-28        kinaba: 				if( J < 0 )
1535d63cea 2011-05-28        kinaba: 					{unsat_case = true; break;}
1535d63cea 2011-05-28        kinaba: 			}
1535d63cea 2011-05-28        kinaba: 			if( !unsat_case ) {
1535d63cea 2011-05-28        kinaba: 				// everyones get M, and J left.
1535d63cea 2011-05-28        kinaba: 				long[] result = new long[money.length];
1535d63cea 2011-05-28        kinaba: 				for(int i=0; i<money.length; ++i)
1535d63cea 2011-05-28        kinaba: 					result[i] = M + (J / money.length) + (i<J%money.length ? 1 : 0);
1535d63cea 2011-05-28        kinaba: 				Arrays.sort(result);
1535d63cea 2011-05-28        kinaba: 				return result;
1535d63cea 2011-05-28        kinaba: 			}
1535d63cea 2011-05-28        kinaba: 		}
1535d63cea 2011-05-28        kinaba: 		{
1535d63cea 2011-05-28        kinaba: 			long J = jackpot;
1535d63cea 2011-05-28        kinaba: 			BigInteger N = BigInteger.valueOf(money.length);
1535d63cea 2011-05-28        kinaba: 			while( J>0 ) {
1535d63cea 2011-05-28        kinaba: 				Arrays.sort(money);
1535d63cea 2011-05-28        kinaba: 
1535d63cea 2011-05-28        kinaba: 				BigInteger sum = BigInteger.ZERO;
1535d63cea 2011-05-28        kinaba: 				for(int i=0; i<money.length; ++i)
1535d63cea 2011-05-28        kinaba: 					sum = sum.add(BigInteger.valueOf(money[i]));
1535d63cea 2011-05-28        kinaba: 				long ave = sum.divide(N).add(BigInteger.ONE).longValue();
1535d63cea 2011-05-28        kinaba: 
1535d63cea 2011-05-28        kinaba: 				long give = ave - money[0];
1535d63cea 2011-05-28        kinaba: 				if( J < give )
1535d63cea 2011-05-28        kinaba: 					give = J;
1535d63cea 2011-05-28        kinaba: 				J -= give;
1535d63cea 2011-05-28        kinaba: 				money[0] += give;
1535d63cea 2011-05-28        kinaba: 			}
1535d63cea 2011-05-28        kinaba: 			Arrays.sort(money);
1535d63cea 2011-05-28        kinaba: 			return money;
1535d63cea 2011-05-28        kinaba: 		}
1535d63cea 2011-05-28        kinaba: 	}
1535d63cea 2011-05-28        kinaba: };