fork download
copy 
  1. // https://m...content-available-to-author-only...h.net/test/read.cgi/tech/1691038333/845
  2.  
  3. #include<iostream>
  4. #include<vector>
  5. #include<map>
  6. #include<string>
  7.  
  8. using UInt = unsigned int;
  9. using ULong = uint64_t;
  10.  
  11. std::string search(UInt m,UInt n,UInt d,const std::vector<UInt>& digits,const std::vector<std::vector<ULong>>& mat){
  12.  
  13.     if(m==0&&n==1&&d==0){
  14.         return "";
  15.     }
  16.  
  17.     auto sum = 0;
  18.     for(auto digit : digits){
  19.         if(digit > m) continue;
  20.  
  21.         auto tmp = mat[m-digit][d-1];
  22.  
  23.         if(sum+tmp>=n){
  24.             return std::to_string(digit)+search(m-digit,n-sum,d-1,digits,mat);
  25.         }else{
  26.             sum+=tmp;
  27.         }
  28.     }
  29.  
  30.     return "0";
  31. }
  32.  
  33. std::string func(UInt m,UInt n,const std::vector<UInt>& digits){
  34.     const auto matSize = std::max<std::size_t>(m,digits.size())+1;
  35.     std::vector<std::vector<ULong>> mat(matSize, std::vector<ULong>(matSize,0));
  36.  
  37.     for(auto digit : digits){
  38.         if(digit<matSize){
  39.             mat[digit][1] = 1;
  40.         }
  41.     }
  42.  
  43.     mat[0][0] = 1;
  44.  
  45.     for(std::size_t i=1; i<matSize; ++i){
  46.         for(std::size_t j=1; j<matSize; ++j){
  47.             for(auto digit : digits){
  48.                 if((i+digit)<matSize && (j+1)<matSize){
  49.                     mat[i+digit][j+1] += mat[i][j];
  50.                 }
  51.             }
  52.         }
  53.     }
  54.  
  55.     UInt d;
  56.     ULong sum = 0;
  57.     for(d=1; d<matSize; ++d){
  58.         if(sum+mat[m][d]>=n){
  59.             break;
  60.         }else{
  61.             sum+=mat[m][d];
  62.         }
  63.     }
  64.  
  65.     if(d == matSize){
  66.         return "0";
  67.     }
  68.  
  69.     return search(m,n-sum,d,digits,mat);
  70. }
  71.  
  72. void test(UInt m,UInt n){
  73.     std::cout << '(' << m << ',' << n << ") -> " << func(m,n,{1,2,3,4,5}) << std::endl;
  74. }
  75.  
  76. int main(){
  77.     test(2,1);
  78.     test(2,2);
  79.     test(2,3);
  80.     test(20,1);
  81.     test(20,2);
  82.     test(20,3);
  83.     test(20,400096);
  84.     test(20,400097);
  85.     test(32,1);
  86.     test(32,2);
  87.     test(32,3);
  88.     test(32,1000);
  89.     test(32,1000'000);
  90.     test(32,1000'000'000);
  91.     test(32,1333'610'936);
  92.     test(32,1333'610'937);
  93.     return 0;
  94. }
Success #stdin #stdout 0s 5324KB
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/ezHz45
language:
C++ (gcc 8.3)
created:
7 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!