We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #76: Counting summations
  4. Discussions

Project Euler #76: Counting summations

  • Problem
  • Submissions
  • Leaderboard
  • Discussions

Sort 12 Discussions, By:

votes
  • recency
  • votes

Please Login in order to post a comment

  • nikhilksingh97 4 years ago+ 1 comment

    It is a bit like coin sums problem....

    4|
    Permalink
    • Argooni 3 years ago+ 0 comments

      Bit is quite an understatement. :)

      3|
      ParentPermalink
  • meArch 5 years ago+ 1 comment

    I have been trying to solve this problem and have got the correct answer on my Ubuntu 64 bit 14.04 machine. But, when I submit the code, it fails for all but 2 of the test cases. I feel I am going wrong with the data type and format specifier. I am using unsigned long long and using %llu or or %"PRIu64" to print the output, but not getting the correct answer. However, on my machine I get all correct answers for all the values upto 1000. Can anyone please guide me for this ?

    2|
    Permalink
    • Kevinagin 3 years ago+ 0 comments

      I have no idea if this could be the source of the problem... but I believe all of the test cases have a line break at the end of the input. Just need to be aware of this when you process the input data.

      0|
      ParentPermalink
  • bhavikgevariya 1 year ago+ 0 comments

    the number of partitions from [0-1000] is here for check some testcase

    0|
    Permalink
  • imtiazemu 2 years ago+ 0 comments

    Getting WA for the Test Case #3. Anyone has any clue?

    unsigned long long int combinations[1001],t,i,j,n;
    #define MOD 1000000007
    
    int main()
    {
        combinations[1001] = {0};
        combinations[0] = 1;
    
        for(i = 1; i < 1000; i++)
            for(j = i; j <= 1000; j++)
                combinations[j] += (combinations[j-i] % MOD);
    
        scanf("%lld",&t);
        for (i=1;i<=t;i++)
        {
            scanf("%lld",&n);
            printf("%lld\n",(combinations[n] % MOD) - 1);
        }
    
        return 0;
    }
    
    0|
    Permalink
  • jt_112 2 years ago+ 0 comments
    #include <bits/stdc++.h>
    #define P 1000000007
    using namespace std;
    
    unsigned long long int getWays(int n)
    {
        vector < unsigned long long int > a(n+1);
        a[0]=1;
        for(int j=1;j<n;j++)
        {
            for(int i=j;i<=n;i++)
            {
                   a[i]+=a[i-j]%P ;
            }
        }
        return a[n]%P;
    }
    
    int main() 
    {
        int t,n;
        cin >> t;
        
        for(int i = 0; i< t;i++){
           cin >> n;
        // Print the number of ways of making change for 'n' units using coins having the values given by 'c'
        unsigned long long int ways = getWays(n);
        cout << ways<<endl;}
        return 0;
    }
    
    0|
    Permalink
  • ErikTillema 2 years ago+ 0 comments

    This is a classical dynamic programming problem. No advanced math needed, if you go that way.

    0|
    Permalink
  • anand_10 2 years ago+ 0 comments

    python test case 3 is not passed due to time out error

    0|
    Permalink
  • jayeshudhani 3 years ago+ 1 comment

    What should be the answer for n=7?

    0|
    Permalink
    • bhavikgevariya 1 year ago+ 0 comments

      7=>14

      image

      0|
      ParentPermalink
  • jamespate 3 years ago+ 1 comment

    I am using Euler's recurrence equation found on the website: http://mathworld.wolfram.com/PartitionFunctionP.html

    For n >= 0 and n <= 200 I first perform a table lookup and if necessary then use the enter the recursive part of the algorithm for n > 200. I timeout on all but the first two test cases. I am using C# with long (64-bit) integers. I could use BigIntegers and take a day to generate a 1001 element table.

    0|
    Permalink
    • cregbAsked to answer 3 years ago+ 0 comments
      1. You will need to use BigInteger or the like. The number of partitions for 1000 is ~2.4e31.

      2. You can calculate all the partition values for 2 through 1000 in a few seconds if you use the right algorithm. The generating algorithm I used is based on MacMahon's recurrence.

      0|
      ParentPermalink
  • kraker 4 years ago+ 0 comments

    for large integers i am getting value in negatives i have used long long int and taken enough care with mod

    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature