Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя BrynzaMasterZa228

Автор BrynzaMasterZa228, история, 20 месяцев назад, По-английски

I just solved a problem that need 3^n recursion 0,1,2 0=not choose, 1=choose one way, 2=choose 2nd way like this, and its messy cause we need the path we took also it itself doesnt seem nice, can you guys please write your ways of writing .

sorry i will reply hours late cause i will sleep rn

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please send the link

»
20 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

You could generate 2^n masks and then iterate over submasks, it'll be 3^n in total (e.g. outer mask 0 => option #1, inner mask 0 => #2, inner mask 1 => #3)

  for (int mask = 0; mask < (1 << n); mask++) {
    for (int sub = mask;; sub = (sub - 1) & mask) {
      /* process */
      if (sub == 0) break;
    }
  }

Or just write a recursion, it's not really much code in modern c++ and a lot more flexible

  vector<int> a(n);
  function<void(int)> rec = [&](int i) {
    if (i < n) {
      for (a[i] = 0; a[i] <= 2; a[i]++) rec(i+1);
    } else {
      /* process */
    }
  };
  rec(0);
»
20 месяцев назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится
int p = power(3, n);
for (int i = 0; i < p; ++i) {
    for (int j = i, k = 0; k < n; j /= 3, ++k) {
        cout << j % 3;
    }
    cout << "\n";
}

Similar to the power of two version but you can't use the bitwise operation here. You can also replace 3 with other positive integer to get a more generalized version.

»
20 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится