ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1044. Lucky Tickets. Easy!

Combinatory solution
Posted by Dmitri Belous 28 Apr 2012 22:46
May be someone need it.

#include<iostream>
#include<math.h>
using namespace std;
int cnk(int k,int n)
{
    double res=1;
    for(int i=1;i<=k;++i)
        res=res*(n-k+i)/i;
    return res;
}
int hnk(int k,int n)
{
    return cnk(k,n+k-1);
}
int main()
{
    int n;
    cin>>n;
    int n_2=n/2,sum,n_9=n_2*9,e,res=0;
    for(int i=0;i<=n_9;++i)
    {
        sum=0;
        e=1;
        for(int j=1;j<=i/10;++j)
        {
            sum+=e*cnk(j,n_2)*hnk(i-j*10,n_2);
            e*=-1;
        }
        res+=pow(hnk(i,n_2)-sum,2.);
    }
    cout<<res;
    return 0;
}

//cnk(k,n)=n!/k!/(n-k)!

Edited by author 28.04.2012 22:48
Re: Combinatory solution
Posted by nushrat 19 Nov 2016 08:19
can you please explain the algorithm of your code ?
Re: Combinatory solution
Posted by Grandmaster 13 Nov 2017 03:05
dynamic solution

#include <iostream>
using namespace std;
int n, dp[10][85], sum;
int main()
{
    cin >> n;
    for(int i = 0; i < 10; i++)
        dp[1][i] = 1;
    for(int i = 2; i <= n / 2; i++)
        for(int j = 0; j <= 81; j++){
            for(int k = 0; k < 10; k++)
                if(k <= j)
                    dp[i][j] += dp[i - 1][j - k];
                if(i == n / 2)
                    sum += dp[i][j] * dp[i][j];
        }
    cout << max(sum, 10);
}