fork download
copy 
  1. /*
  2.  *   Generate all strings for a given n that use the first n letters of
  3.  *   the alphabet with a used once, b used twice, etc., and that don't
  4.  *   have consecutive identical letters.
  5.  */
  6. #include <iostream>
  7. #include <cstdlib>
  8. #include <map>
  9. using namespace std ;
  10. const int MAXN = 30 ;
  11. const int MAXSUM = MAXN * (MAXN + 1) / 2 ;
  12. int n ;
  13. int sum ;
  14. long long ii ;
  15. char str[MAXSUM+1] ;
  16. int used[MAXN] ;
  17. long long cnt ;
  18. unsigned long long mpow[MAXN] ;
  19. typedef pair<int, unsigned long long> keytype ;
  20. map<keytype, long long> increment ;
  21. long long target ;
  22. char seen = 0 ;
  23. void recur(int at, int prev, int powsum, int distinct, unsigned long long cnts) {
  24.    if (cnt > target)
  25.       return ;
  26.    if (at == sum) {
  27.       if (powsum + n + 2 == (2 << n) && distinct == n) {
  28.          cnt++ ;
  29.          if (cnt == target) {
  30.             cout << str << endl ;
  31.             seen = 1 ;
  32.          }
  33.       }
  34.       return ;
  35.    }
  36.    keytype key = make_pair(at*100+used[prev], cnts) ;
  37.    if (increment.find(key) != increment.end()) {
  38.       long long inc = increment[key] ;
  39.       if (inc + cnt < target) {
  40.          cnt += increment[key] ;
  41.          return ;
  42.       }
  43.    }
  44.    long long ocnt = cnt ;
  45.    for (int i=0; i<26; i++)
  46.       if (i != prev) {
  47.          int u = used[i] ;
  48.          if (powsum + (1 << u) + n + 2 <= (2 << n) && (u || distinct < n)) {
  49.             str[at] = 'a' + i ;
  50.             used[i]++ ;
  51.             recur(at+1, i, powsum + (1 << u), distinct + (u == 0),
  52.                   cnts + mpow[u]) ;
  53.             used[i]-- ;
  54.          }
  55.       }
  56.    increment[key] = cnt - ocnt ;
  57. }
  58. int main(int argc, char *argv[]) {
  59.    cin >> n >> target ;
  60.    sum = n * (n + 1) / 2 ;
  61.    mpow[0] = 1 ;
  62.    for (int i=0; i<n; i++)
  63.       mpow[i+1] = ((unsigned long long)(n+1)) * mpow[i] ;
  64.    recur(0, 27, 0, 0, 0) ;
  65.    if (!seen)
  66.       cout << -1 << endl ;
  67. }
  68.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/hybYQH
language:
C++ (gcc 8.3)
created:
3 days 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!