nikhilksingh97 It is a bit like coin sums problem....
Argooni Bit is quite an understatement. :)
meArch 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 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 the number of partitions from [0-1000] is here for check some testcase
imtiazemu 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 #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 This is a classical dynamic programming problem. No advanced math needed, if you go that way.
anand_10 python test case 3 is not passed due to time out error
jayeshudhani What should be the answer for n=7?
bhavikgevariya 7=>14
jamespate 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 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 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