fork download
copy 
  1. #include <boost/multiprecision/cpp_int.hpp>
  2. #include <iostream>
  3. #include <vector>
  4. class f845 {
  5.   using bigint = boost::multiprecision::cpp_int;
  6.   std::vector<std::vector<bigint> > cc;
  7.   bigint count_permutations(int s, int w) {
  8.     if (s < 1 || w < 1 || s < w || w * 5 < s) {
  9.       return 0;
  10.     } else if (s <= 5 && w == 1) {
  11.       return 1;
  12.     } else if (0 < cc[s][w]) {
  13.       return cc[s][w];
  14.     } else {
  15.       bigint c = 0;
  16.       for (int d = 1; d <= 5; d++)
  17.         c += count_permutations(s - d, w - 1);
  18.       return cc[s][w] = c;
  19.     }
  20.   }
  21.   bigint aux(bigint n, bigint acc, bigint b, int s, int w) {
  22.     if (s < 1 || w < 1) {
  23.       return acc;
  24.     } else if (w == 1) {
  25.       return acc * 10 + s;
  26.     } else {
  27.       for (int d = 1; d <= 5; d++) {
  28.         bigint c = count_permutations(s - d, w - 1);
  29.         if (n <= b + c)
  30.           return aux(n, acc * 10 + d, b, s - d, w - 1);
  31.         b += c;
  32.       }
  33.       return -1;
  34.     }
  35.   }
  36. public:
  37.   f845(int m) : cc(m + 1, std::vector<bigint>(m + 1, 0)) {}
  38.   bigint operator()(int m, bigint n) {
  39.     bigint b = 0;
  40.     if (0 < m && 0 < n) for (int w = 1; w <= m; w++) {
  41.       bigint c = count_permutations(m, w);
  42.       if (n <= b + c)
  43.         return aux(n, 0, b, m, w);
  44.       b += c;
  45.     }
  46.     return 0;
  47.   }
  48. };
  49. int main() {
  50.   using bigint = boost::multiprecision::cpp_int;
  51.   //auto f = f845(2000);
  52.   //auto g = [&f](int m, bigint n) {
  53.   //  std::cout << "(" << m << "," << n << ") → " << f(m, n) << std::endl;
  54.   //};
  55.   auto g = [](int m, bigint n) {
  56.     auto f = f845(m);
  57.     std::cout << "(" << m << "," << n << ") → " << f(m, n) << std::endl;
  58.   };
  59.   /*
  60.   g(-1,1);
  61.   g(1,-1);
  62.   g(-1,-1);
  63.   g(2,1);
  64.   g(2,2);
  65.   g(2,3);
  66.   g(20,1);
  67.   g(20,2);
  68.   g(20,3);
  69.   g(20,400096);
  70.   g(20,400097);
  71.   g(32,1);
  72.   g(32,2);
  73.   g(32,3);
  74.   g(32,1000);
  75.   g(32,1000000);
  76.   g(32,1000000000);
  77.   g(32,1333610936);
  78.   g(32,1333610937);
  79.   */
  80.   g(2000,(bigint)1 << 1024);
  81.   return 0;
  82. }
  83.  
Success #stdin #stdout 0.21s 146744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(2000,179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216) → 133455533351454245243544545545533544533353455351551354434255345155535155553543255433542555343535545355541554555135355524435524344435532524545543525545533451134455552254455333442334354534523153425445155555435153554255552353344553554445354545514355554555554435333353123555345255242334345515554533345534425455553521553555455455545441241132525455435442255542322515454522545115515532453523344525423555455451555554153554555544451254441554323215525455545135444445535554555545425522544345243455524545444534534551543444144
https://ideone.com/f62fkG
language:
C++ (gcc 8.3)
created:
10 hours 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!