3.6 years ago

Ujjwal Rana 50

Approach

We can simulate the whole process by brute force. First we allot the i candies to the first child, then out of remaining s-i candies we allot j to the second child. Now if the number of candies left are less than or equal to K we can allot the remaining candies to the third child and we get a valid allotment.Otherwise we get an invalid allotment.

Time Complexity - O(K^2)

Pseudocode

ll ans=0;
 for(ll i(0);i<=min(s,k);++i){ // alloting to first child
    for(ll j(0);j<=min(k,s-i);++j){ // alloting to second child
        ans+=(k>=(s-i-j)); // checking if the allotment is valid
    }
 }
 return ans;

3.6 years ago

sandeep agri • 0

//DP solution    
 #include <bits/stdc++.h>
    using namespace std;
    int t[3][50001];
    int solve(int k,int s,int i)
    {
        if(i>=3)
        {
            if(s==0) return 1;
            return 0;
        }
        int ans=0;
        if(t[i][s]!=-1) return t[i][s];
        for(int x=0;x<=k;x++)
        {
            ans+=solve(k,s-x,i+1);
        }
        return t[i][s]=ans;
    }
    int main() {
        int k,s;
        cin>>k>>s;
        memset(t,-1,sizeof(t));
        cout<