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;
}
}
};