Artifact 40bffdccb4631d6990664d0b7e991baba6ea00fa:
0000: 69 6d 70 6f 72 74 20 6a 61 76 61 2e 6d 61 74 68 import java.math
0010: 2e 2a 3b 0d 0a 69 6d 70 6f 72 74 20 6a 61 76 61 .*;..import java
0020: 2e 75 74 69 6c 2e 2a 3b 0d 0a 0d 0a 70 75 62 6c .util.*;....publ
0030: 69 63 20 63 6c 61 73 73 20 54 68 65 4a 61 63 6b ic class TheJack
0040: 70 6f 74 44 69 76 4f 6e 65 20 7b 0d 0a 09 70 75 potDivOne {...pu
0050: 62 6c 69 63 20 6c 6f 6e 67 5b 5d 20 66 69 6e 64 blic long[] find
0060: 28 6c 6f 6e 67 5b 5d 20 6d 6f 6e 65 79 2c 20 6c (long[] money, l
0070: 6f 6e 67 20 6a 61 63 6b 70 6f 74 29 0d 0a 09 7b ong jackpot)...{
0080: 0d 0a 09 09 6c 6f 6e 67 20 4d 20 3d 20 30 3b 0d ....long M = 0;.
0090: 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
00a0: 69 3c 6d 6f 6e 65 79 2e 6c 65 6e 67 74 68 3b 20 i<money.length;
00b0: 2b 2b 69 29 0d 0a 09 09 09 69 66 28 20 4d 20 3c ++i).....if( M <
00c0: 20 6d 6f 6e 65 79 5b 69 5d 20 29 0d 0a 09 09 09 money[i] ).....
00d0: 09 4d 20 3d 20 6d 6f 6e 65 79 5b 69 5d 3b 0d 0a .M = money[i];..
00e0: 0d 0a 09 09 62 6f 6f 6c 65 61 6e 20 75 6e 73 61 ....boolean unsa
00f0: 74 5f 63 61 73 65 20 3d 20 66 61 6c 73 65 3b 0d t_case = false;.
0100: 0a 09 09 7b 0d 0a 09 09 09 6c 6f 6e 67 20 4a 20 ...{.....long J
0110: 3d 20 6a 61 63 6b 70 6f 74 3b 0d 0a 09 09 09 66 = jackpot;.....f
0120: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6d 6f or(int i=0; i<mo
0130: 6e 65 79 2e 6c 65 6e 67 74 68 3b 20 2b 2b 69 29 ney.length; ++i)
0140: 20 7b 0d 0a 09 09 09 09 4a 20 2d 3d 20 4d 2d 6d {......J -= M-m
0150: 6f 6e 65 79 5b 69 5d 3b 0d 0a 09 09 09 09 69 66 oney[i];......if
0160: 28 20 4a 20 3c 20 30 20 29 0d 0a 09 09 09 09 09 ( J < 0 ).......
0170: 7b 75 6e 73 61 74 5f 63 61 73 65 20 3d 20 74 72 {unsat_case = tr
0180: 75 65 3b 20 62 72 65 61 6b 3b 7d 0d 0a 09 09 09 ue; break;}.....
0190: 7d 0d 0a 09 09 09 69 66 28 20 21 75 6e 73 61 74 }.....if( !unsat
01a0: 5f 63 61 73 65 20 29 20 7b 0d 0a 09 09 09 09 2f _case ) {....../
01b0: 2f 20 65 76 65 72 79 6f 6e 65 73 20 67 65 74 20 / everyones get
01c0: 4d 2c 20 61 6e 64 20 4a 20 6c 65 66 74 2e 0d 0a M, and J left...
01d0: 09 09 09 09 6c 6f 6e 67 5b 5d 20 72 65 73 75 6c ....long[] resul
01e0: 74 20 3d 20 6e 65 77 20 6c 6f 6e 67 5b 6d 6f 6e t = new long[mon
01f0: 65 79 2e 6c 65 6e 67 74 68 5d 3b 0d 0a 09 09 09 ey.length];.....
0200: 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c .for(int i=0; i<
0210: 6d 6f 6e 65 79 2e 6c 65 6e 67 74 68 3b 20 2b 2b money.length; ++
0220: 69 29 0d 0a 09 09 09 09 09 72 65 73 75 6c 74 5b i).......result[
0230: 69 5d 20 3d 20 4d 20 2b 20 28 4a 20 2f 20 6d 6f i] = M + (J / mo
0240: 6e 65 79 2e 6c 65 6e 67 74 68 29 20 2b 20 28 69 ney.length) + (i
0250: 3c 4a 25 6d 6f 6e 65 79 2e 6c 65 6e 67 74 68 20 <J%money.length
0260: 3f 20 31 20 3a 20 30 29 3b 0d 0a 09 09 09 09 41 ? 1 : 0);......A
0270: 72 72 61 79 73 2e 73 6f 72 74 28 72 65 73 75 6c rrays.sort(resul
0280: 74 29 3b 0d 0a 09 09 09 09 72 65 74 75 72 6e 20 t);......return
0290: 72 65 73 75 6c 74 3b 0d 0a 09 09 09 7d 0d 0a 09 result;.....}...
02a0: 09 7d 0d 0a 09 09 7b 0d 0a 09 09 09 6c 6f 6e 67 .}....{.....long
02b0: 20 4a 20 3d 20 6a 61 63 6b 70 6f 74 3b 0d 0a 09 J = jackpot;...
02c0: 09 09 42 69 67 49 6e 74 65 67 65 72 20 4e 20 3d ..BigInteger N =
02d0: 20 42 69 67 49 6e 74 65 67 65 72 2e 76 61 6c 75 BigInteger.valu
02e0: 65 4f 66 28 6d 6f 6e 65 79 2e 6c 65 6e 67 74 68 eOf(money.length
02f0: 29 3b 0d 0a 09 09 09 77 68 69 6c 65 28 20 4a 3e );.....while( J>
0300: 30 20 29 20 7b 0d 0a 09 09 09 09 41 72 72 61 79 0 ) {......Array
0310: 73 2e 73 6f 72 74 28 6d 6f 6e 65 79 29 3b 0d 0a s.sort(money);..
0320: 0d 0a 09 09 09 09 42 69 67 49 6e 74 65 67 65 72 ......BigInteger
0330: 20 73 75 6d 20 3d 20 42 69 67 49 6e 74 65 67 65 sum = BigIntege
0340: 72 2e 5a 45 52 4f 3b 0d 0a 09 09 09 09 66 6f 72 r.ZERO;......for
0350: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6d 6f 6e 65 (int i=0; i<mone
0360: 79 2e 6c 65 6e 67 74 68 3b 20 2b 2b 69 29 0d 0a y.length; ++i)..
0370: 09 09 09 09 09 73 75 6d 20 3d 20 73 75 6d 2e 61 .....sum = sum.a
0380: 64 64 28 42 69 67 49 6e 74 65 67 65 72 2e 76 61 dd(BigInteger.va
0390: 6c 75 65 4f 66 28 6d 6f 6e 65 79 5b 69 5d 29 29 lueOf(money[i]))
03a0: 3b 0d 0a 09 09 09 09 6c 6f 6e 67 20 61 76 65 20 ;......long ave
03b0: 3d 20 73 75 6d 2e 64 69 76 69 64 65 28 4e 29 2e = sum.divide(N).
03c0: 61 64 64 28 42 69 67 49 6e 74 65 67 65 72 2e 4f add(BigInteger.O
03d0: 4e 45 29 2e 6c 6f 6e 67 56 61 6c 75 65 28 29 3b NE).longValue();
03e0: 0d 0a 0d 0a 09 09 09 09 6c 6f 6e 67 20 67 69 76 ........long giv
03f0: 65 20 3d 20 61 76 65 20 2d 20 6d 6f 6e 65 79 5b e = ave - money[
0400: 30 5d 3b 0d 0a 09 09 09 09 69 66 28 20 4a 20 3c 0];......if( J <
0410: 20 67 69 76 65 20 29 0d 0a 09 09 09 09 09 67 69 give ).......gi
0420: 76 65 20 3d 20 4a 3b 0d 0a 09 09 09 09 4a 20 2d ve = J;......J -
0430: 3d 20 67 69 76 65 3b 0d 0a 09 09 09 09 6d 6f 6e = give;......mon
0440: 65 79 5b 30 5d 20 2b 3d 20 67 69 76 65 3b 0d 0a ey[0] += give;..
0450: 09 09 09 7d 0d 0a 09 09 09 41 72 72 61 79 73 2e ...}.....Arrays.
0460: 73 6f 72 74 28 6d 6f 6e 65 79 29 3b 0d 0a 09 09 sort(money);....
0470: 09 72 65 74 75 72 6e 20 6d 6f 6e 65 79 3b 0d 0a .return money;..
0480: 09 09 7d 0d 0a 09 7d 0d 0a 7d 3b 0d 0a ..}...}..};..