# Project Euler #76: Counting summations

# Project Euler #76: Counting summations

nikhilksingh97 + 1 comment It is a bit like coin sums problem....

Argooni + 0 comments Bit is quite an understatement. :)

meArch + 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 ?

Kevinagin + 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.

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

imtiazemu + 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; }

jt_112 + 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; }

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

anand_10 + 0 comments python test case 3 is not passed due to time out error

jayeshudhani + 1 comment What should be the answer for n=7?

bhavikgevariya + 0 comments 7=>14

jamespate + 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.

cregbAsked to answer + 0 comments You will need to use BigInteger or the like. The number of partitions for 1000 is ~2.4e31.

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.

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

Sort 12 Discussions, By:

Please Login in order to post a comment