fork download
copy 
  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4.  
  5. int width;
  6. int blockSize;
  7. static std::vector<double> memoize;
  8.  
  9. double pStdCap(int n, int m, int myMax) {
  10.  
  11.     if (myMax * m < n || n < m) return 0;
  12.     if (myMax * m == n || n <= m + 1) return 1;
  13.     if (m < 2) return m;
  14.  
  15.     const int block = myMax * blockSize + (n - m) * width + m - 2;
  16.     if (memoize[block]) return memoize[block];
  17.  
  18.     int niter = n / m;
  19.  
  20.     if (m == 2) {
  21.         if (myMax * 2 >= n) {
  22.             myMax = std::min(myMax, n - 1);
  23.             return niter - (n - 1 - myMax);
  24.         } else {
  25.             return 0;
  26.         }
  27.     }
  28.  
  29.     double count = 0;
  30.  
  31.     for (; niter--; n -= m, --myMax) {
  32.         count += (memoize[myMax * blockSize + (n - m) * width + m - 3] = pStdCap(n - 1, m - 1, myMax));
  33.     }
  34.  
  35.     return count;
  36. }
  37.  
  38. double CountPartLenCap(int n, int m, int myMax) {
  39.  
  40.     if (myMax * m < n || n < m) return 0;
  41.     if (myMax * m == n || n <= m + 1) return 1;
  42.     if (m < 2) return m;
  43.  
  44.     if (m == 2) {
  45.         if (myMax * 2 >= n) {
  46.             myMax = std::min(myMax, n - 1);
  47.             return n / m - (n - 1 - myMax);
  48.         } else {
  49.             return 0;
  50.         }
  51.     }
  52.  
  53.     width = m;
  54.     blockSize = m * (n - m + 1);
  55.     memoize = std::vector<double>((myMax + 1) * blockSize, 0.0);
  56.  
  57.     return pStdCap(n, m, myMax);
  58. }
  59.  
  60. int main() {
  61. 	std::cout << "Here are the 5 4-length partitions of 10 with a max of 4\n";
  62. 	std::cout << "1, 1, 4, 4\n1, 2, 3, 4\n";
  63. 	std::cout << "1, 3, 3, 3\n2, 2, 2, 4\n";
  64. 	std::cout << "2, 2, 3, 3\nThe function properly returns 5\n";
  65. 	std::cout << CountPartLenCap(10, 4, 4) << std::endl;
  66. 	std::cout << "The function instantly returns the number of 15-length partitions of 100 with a max of 15\n";
  67. 	std::cout << CountPartLenCap(100, 15, 15) << std::endl;
  68. 	std::cout << "While the below computes without exceeding the time limit, it probably isn't very useful\n";
  69. 	std::cout << CountPartLenCap(10000, 40, 300) << std::endl;
  70. 	return 0;
  71. }
Success #stdin #stdout 4.37s 940544KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Here are the 5 4-length partitions of 10 with a max of 4
1, 1, 4, 4
1, 2, 3, 4
1, 3, 3, 3
2, 2, 2, 4
2, 2, 3, 3
The function properly returns 5
5
The function instantly returns the number of 15-length partitions of 100 with a max of 15
927060
While the below computes without exceeding the time limit, it probably isn't very useful
3.21315e+37
https://ideone.com/c3WohV
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!