#include #include #include #include #include #include using namespace std; int nDice; long* powersOfSix; long** howManyWays; ///< howManyWays[k][n] how many ways to roll a total of n using k dice void solve (istream& in) { in >> nDice; powersOfSix = new long[nDice+1]; powersOfSix[0] = 1; for (int i = 1; i <= nDice; ++i) { powersOfSix[i] = 6 * powersOfSix[i-1]; if (powersOfSix[i] <= powersOfSix[i-1]) { cerr << "Numerical error computing 6^" << i << " = 6*" << powersOfSix[i-1] << " yielded " << powersOfSix[i] << endl; cerr << "Compare to max of " << numeric_limits::max() << endl; } } howManyWays = new long*[nDice+1]; howManyWays[0] = new long[6*nDice]; fill_n(howManyWays[0], 6*nDice+1, 0L); howManyWays[1] = new long[6*nDice+1]; fill_n(howManyWays[1], 6*nDice+1, 0L); fill_n(howManyWays[1]+1, 6, 1L); long boundsCheck = 0L; for (int dice = 2; dice <= nDice; ++dice) { howManyWays[dice] = new long[6*nDice+1]; for (int n = 0; n < nDice; ++n) howManyWays[dice][n] = 0; for (int n = dice; n <= 6*dice; ++n) { long sum = 0L; for (int i = 1; i <= 6; ++i) { if (i < n) sum += howManyWays[dice-1][n-i]; } howManyWays[dice][n] = sum; /* cerr << dice << " dice can roll " << n << " in " << sum << " ways." << endl; */ boundsCheck = max(boundsCheck, sum); } for (int n = 6*dice+1; n <= 6*nDice; ++n) howManyWays[dice][n] = 0; } int target; in >> target; int rolled[6]; fill_n (rolled, 6, 0); int initialSum = 0; for (int i = 0; i < nDice; ++i) { int k; in >> k; ++rolled[k-1]; initialSum += k; } if (initialSum == target) { cout << 0 << endl; return; } int pickingUp[6]; fill_n (pickingUp, 6, 0); long bestNumerator = 0; int bestDice = 0; while (true) { // Remove one more die int k = 0; while (k < 6) { if (rolled[k] > pickingUp[k]) { // Pick up a die of value k+1 ++pickingUp[k]; break; } else { // Put back all dice of value k+1 and consider picking up // a higher-numbered die. pickingUp[k] = 0; ++k; } } if (k >= 6) break; int pickedUpValue = pickingUp[0] + 2*pickingUp[1] + 3*pickingUp[2] + 4*pickingUp[3] + 5*pickingUp[4] + 6*pickingUp[5]; int remainingSum = initialSum - pickedUpValue; int nPickedUp = pickingUp[0] + pickingUp[1] + pickingUp[2] + pickingUp[3] + pickingUp[4] + pickingUp[5]; if (target > remainingSum) { long numerator = howManyWays[nPickedUp][target-remainingSum]; numerator *= powersOfSix[nDice-nPickedUp]; long compare = bestNumerator - numerator; if (compare < 0 || (compare == 0 && nPickedUp < bestDice)) { bestDice = nPickedUp; bestNumerator = numerator; /* cerr << " Picking up " << bestDice << " of value " << pickedUpValue << " gives probability " << bestNumerator << "/" << powersOfSix[nDice] << endl; */ } } } cout << bestDice << endl; } int main (int argc, char** argv) { if (argc > 1) { ifstream in (argv[1]); solve (in); } else solve (cin); }