fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. string nthPartition(int m, int n)
  7. {
  8.     vector<vector<int>> A(m, vector<int>(m, 0));
  9.     fill_n(A[0].begin(), min(m, 5), 1);
  10.     for (int i = 1; i < m; i++) {
  11.         int j = 0;
  12.         while (++j < m) A[i][j] = A[i][j - 1] + A[i - 1][j - 1];
  13.         while (--j > 5) A[i][j] -= A[i][j - 5];
  14.     }
  15.  
  16.     int L;
  17.     for (L = 1; L <= m; L++) {
  18.         if (n <= A[L - 1][m - 1]) break;
  19.         if (L < m) {
  20.             n -= A[L - 1][m - 1];
  21.         } else {
  22.             return "0";
  23.         }
  24.     }
  25.  
  26.     string a(L, '0');
  27.     for (int i = 0; i < L; i++) {
  28.         int j;
  29.         for (j = 1; j <= 5; j++) {
  30.             if (i < L - 1) {
  31.                 if (n <= A[L - i - 2][m - j - 1]) break;
  32.                 n -= A[L - i - 2][m - j - 1];
  33.             } else {
  34.                 if (j == m) break;
  35.             }
  36.         }
  37.  
  38.         a[i] += j;
  39.         m -= j;
  40.     }
  41.  
  42.     return a;
  43. }
  44.  
  45. int Q[][2] = {
  46.     {2, 1}, {2, 2}, {2, 3},
  47.     {20, 1}, {20, 2}, {20, 3}, {20, 400096}, {20, 400097},
  48.     {32, 1}, {32, 2}, {32, 3}, {32, 1000}, {32, 1000000}, {32, 1000000000}, {32, 1333610936}, {32, 1333610937}
  49. };
  50.  
  51. int main(void)
  52. {
  53.     for (auto [m, n] : Q) cout << "(" << m << ", " << n << ") → " << nthPartition(m, n) << endl;
  54.     return 0;
  55. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(2, 1) → 2
(2, 2) → 11
(2, 3) → 0
(20, 1) → 5555
(20, 2) → 14555
(20, 3) → 15455
(20, 400096) → 11111111111111111111
(20, 400097) → 0
(32, 1) → 2555555
(32, 2) → 3455555
(32, 3) → 3545555
(32, 1000) → 34355354
(32, 1000000) → 11532334334
(32, 1000000000) → 2141111311212411131
(32, 1333610936) → 11111111111111111111111111111111
(32, 1333610937) → 0
https://ideone.com/I6K1tl
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
secret

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!