Euler Projesi 240. Soru

En Yüksek Zar

Beş adet 6-yüzlü zar (1'den 6'ya kadar numaralı) atıldığında  üste gelen en yüksek 3 sayının toplamının 15 olmasının 1111 farklı yolu vardır. Bazıları aşağıdaki gibidir:

D1, D2, D3, D4, D5 = 4,3,6,3,5
D1, D2, D3, D4, D5 = 4,3,3,5,6
D1, D2, D3, D4, D5 = 3,3,3,6,6
D1, D2, D3, D4, D5 = 6,6,3,3,3

Yirmi adet 12-yüzlü zar (1'den 12'ye kadar numaralı) atıldığında en yüksek 10 sayının toplamının 70 olmasının kaç farklı yolu vardır?
Cevap: 7448717393364181966

Java:

import static java.lang.Math.*;

public class Problem240 {
    static int[] cnt;
    static long res;

    static void solve() {
        int k = 0, sum = 0;
        for (int i = 12; i >= 1 && k < 10; --i) {
            int x = min(10-k, cnt[i]);
            k += x;
            sum += x*i;
        }
        if (sum == 70)
            res += Util.binomKoef(cnt);
    }

    static void rec(int at, int left) {
        if (at == 12) {
            cnt[at] = left;
            solve();
            return;
        }
        for (int i = 0; i <= left; ++i) {
            cnt[at] = i;
            rec(at+1, left-i);
        }
    }

    public static void main(String[] args) {
        cnt = new int[13];
        rec(1, 20);
        System.out.println(res);
    }
}

Mathematica:

cntconfig[l_, d_] := 
 Binomial[d, l[[1, 2]]] If[Length[l] > 1, 
   cntconfig[Drop[l, 1], d - l[[1, 2]]], 
   If[d == l[[1, 2]], 1, (l[[1, 1]] - 1)^(d - l[[1, 2]])]]

cntall[list_, d_] := 
 Sum[Sum[cntconfig[Tally[i], d], {i, 
    FoldList[Append, el, Table[el[[-1]], {d - Length[el]}]]}], {el, 
   list}]

cntall[IntegerPartitions[
   70, {10}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}], 20]

Python:

import math

k = 10
kk = 20
ss = 70

def cnt(a):
    cc = math.factorial(sum(a))
    for i in reversed(range(len(a))):
        cc //= math.factorial(a[i])
    return cc

c = 0
a = 12 * [0]

def f(m, n, ca, sa):
    global c
    for i in reversed(range(n + 1)):
        a[m] = i
        sa += (m + 1) * min(i, max(k - ca, 0))
        ca += i
        if ca <= kk and sa <= ss:
            if m == 0:
                if ca == kk and sa == ss:
                    c += cnt(a)
            else:
                f(m - 1, n - i, ca, sa)
        ca -= i
        sa -= (m + 1) * min(i, max(k - ca, 0))
        a[m] = 0

f(len(a) - 1, kk, 0, 0)

print(c)

C++:

#include 


int main()  {

    int h,k,n,s,d,c,M,res,i,j;
    unsigned long long int sum,dp[21][13][11][71],b[21][21],power[21][21],MOD;
    
    for(i=0;i<=20;i++)  {
        power[i][0]=1;
        for(j=1;j<=20;j++)  power[i][j]=i*power[i][j-1];
    }
    for(n=0;n<=20;n++)  {
        b[n][0]=1;
        b[n][n]=1;
        for(k=1;k=h))  sum+=b[d][c]*power[M-1][d-c];
                        else if((res>0)&&(c<=h))        sum+=b[d][c]*dp[d-c][M-1][h-c][s-M*c];
                    }
                if((k>0)&&(h>0)) dp[d][k][h][s]=sum;
                else  dp[d][k][h][s]=((s==0)&&(h==0));
    }}}}
    printf("%llu\n",dp[20][12][10][70]);
    return 0;
}

C#:

static long Factorial(long n)
 {
 long p = 1;
 while (n > 0)
  p *= n--;
 return p;
 }

// given bin to place die (slot i is number of die with value i+1)
// and max face on die, and dieCount number of dice left to roll, 
// find ways to do it
static long Recurse(long[] bin, long max, long dieCount)
 {
 if (dieCount >= 10)
  { // check cutoff here
  long sum = 0;
  for (int i = 0; i < bin.Length; ++i)
   sum += (i + 1) * bin[i];
  if (sum > 70)
   return 0;
  if ((dieCount == 10) && (sum != 70))
   return 0;
  }
 if (dieCount == 0)
  { // compute multinomial
  long n = bin.Sum();
  long p = Factorial(n);
  foreach (long k in bin)
   p /= Factorial(k);
  return p;
  }
 // base recurse - do another die
 long total = 0;
 for (int roll = 1; roll <= max; ++roll)
  {
  bin[roll - 1] += 1; // add die
  // recurse with one less capped highest die
  total += Recurse(bin, roll, dieCount - 1); 
  bin[roll - 1] -= 1; // remove die
  }
 return total;
 }

static public void Run(bool sample)
 {
 long total = Recurse(new long[12], 12, 20);
 Console.WriteLine("{0}=7448717393364181966", total);
 }

Maple:

phi:=proc(nmin,sigma,k,dmax) option remember; 
if k=0 and sigma=0 then 1
elif k<0 nmin="" or="">dmax then 0 
else add(binomial(k,alpha)*phi(nmin+1,sigma-alpha*nmin,k-alpha,dmax),alpha=0..floor(sigma/nmin)) 
fi 
end:
add(add(add(binomial(20,k)*binomial(20-k,10-k+alpha)*(a10-1)**(10-k+alpha)*phi(a10+1,70-alpha*a10,10-alpha,12),k=alpha..10+alpha),alpha=1..10),a10=1..7);