fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<map>
  4. #include<string>
  5.  
  6. using UInt = unsigned int;
  7. using ULong = uint64_t;
  8.  
  9. ULong factorial(UInt n){
  10.     return (n<=1)?1:n*factorial(n-1);
  11. }
  12.  
  13. ULong pow10(UInt x){
  14.     return (x==0)?1:10*pow10(x-1);
  15. }
  16.  
  17. std::map<UInt,UInt> s2m(const std::string& s){
  18.     std::map<UInt,UInt> res;
  19.     for(auto c : s){
  20.         auto d = c-'0';
  21.         if(d<1||d>9){
  22.             return {};
  23.         }else{
  24.             ++res[d];
  25.         }
  26.     }
  27.     return res;
  28. }
  29.  
  30. std::string m2s(const std::map<UInt,UInt>& m){
  31.     std::string res;
  32.     for(auto& [k,v] : m){
  33.         res += std::string(v,'0'+k);
  34.     }
  35.     return res;
  36. }
  37.  
  38. ULong count(const std::map<UInt,UInt>& digits){
  39.     UInt n = 0;
  40.     ULong a = 1,b = 1;
  41.     for(auto [k,v] : digits){
  42.         n += v;
  43.         b *= factorial(v);
  44.     }
  45.     a = factorial(n);
  46.     return a/b;
  47. }
  48.  
  49. ULong func(const std::map<UInt,UInt>& digits,ULong n){
  50.     if(digits.empty()){
  51.         return 0;
  52.     }
  53.  
  54.     ULong place = [&](){
  55.         UInt p = 0;
  56.         for(auto [digit,num] : digits){
  57.             p += num;
  58.         }
  59.         return pow10(p-1);
  60.     }();
  61.  
  62.     ULong sum = 0;
  63.     for(auto [digit,num] : digits){
  64.         auto nextDigits = digits;
  65.  
  66.         if(num==1){
  67.             nextDigits.erase(digit);
  68.         }else{
  69.             nextDigits[digit] = num-1;
  70.         }
  71.  
  72.         auto m = count(nextDigits);
  73.  
  74.         if(sum+m >= n){
  75.             auto lower = func(nextDigits,n-sum);
  76.             return digit*place + lower;
  77.         }else{
  78.             sum += m;
  79.         }
  80.     }
  81.  
  82.     return 0;
  83. }
  84.  
  85. void test(const std::string& s,const std::vector<ULong>& nList){
  86.     std::cout << s << std::endl;
  87.     auto m = s2m(s);
  88.  
  89.     for(auto n : nList){
  90.         std::cout << n << " -> " << func(m,n) << std::endl;
  91.     }
  92.     std::cout << std::endl;
  93. }
  94.  
  95. int main(){
  96.  
  97.     test("123456789",{1,2,3,123456,234567,362880});
  98.  
  99.     test("111222333444",{1,2,3,123456,234567,369600});
  100.  
  101.     test("112233445566778899",{1,2,3,123456,234567,12504636144000});
  102.  
  103.     return 0;
  104. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
123456789
1 -> 123456789
2 -> 123456798
3 -> 123456879
123456 -> 416589732
234567 -> 684753219
362880 -> 987654321

111222333444
1 -> 111222333444
2 -> 111222334344
3 -> 111222334434
123456 -> 222331434114
234567 -> 324424331112
369600 -> 444333222111

112233445566778899
1 -> 112233445566778899
2 -> 112233445566778989
3 -> 112233445566778998
123456 -> 112233454779958866
234567 -> 112233457875498966
12504636144000 -> 998877665544332211
https://ideone.com/JLM8r8
language:
C++ (gcc 8.3)
created:
23 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!