Artifact Content
Not logged in

Artifact 40bffdccb4631d6990664d0b7e991baba6ea00fa


import java.math.*;
import java.util.*;

public class TheJackpotDivOne {
	public long[] find(long[] money, long jackpot)
	{
		long M = 0;
		for(int i=0; i<money.length; ++i)
			if( M < money[i] )
				M = money[i];

		boolean unsat_case = false;
		{
			long J = jackpot;
			for(int i=0; i<money.length; ++i) {
				J -= M-money[i];
				if( J < 0 )
					{unsat_case = true; break;}
			}
			if( !unsat_case ) {
				// everyones get M, and J left.
				long[] result = new long[money.length];
				for(int i=0; i<money.length; ++i)
					result[i] = M + (J / money.length) + (i<J%money.length ? 1 : 0);
				Arrays.sort(result);
				return result;
			}
		}
		{
			long J = jackpot;
			BigInteger N = BigInteger.valueOf(money.length);
			while( J>0 ) {
				Arrays.sort(money);

				BigInteger sum = BigInteger.ZERO;
				for(int i=0; i<money.length; ++i)
					sum = sum.add(BigInteger.valueOf(money[i]));
				long ave = sum.divide(N).add(BigInteger.ONE).longValue();

				long give = ave - money[0];
				if( J < give )
					give = J;
				J -= give;
				money[0] += give;
			}
			Arrays.sort(money);
			return money;
		}
	}
};