洛谷 P1096 Hanoi 双塔问题

// 洛谷 P1096 Hanoi 双塔问题 —— 第 ① 版：把 2n 个盘当成普通汉诺塔（**这一版是错的**）
//
// 输入：n（A 柱上有 2n 个盘子，共 n 种尺寸，每种两个）
// 输出：本该是最少移动次数
//
// 这份为什么存在：刚学完第 2 章的汉诺塔，看到「2n 个圆盘」，
// 手比脑子快 —— 直接套公式 2^(盘数) − 1 = 2^(2n) − 1。
//
// ⚠ 错在哪：**这两个同尺寸的圆盘是不加区分的**（题面第一句就写了）。
//    普通汉诺塔要求「上小下大」且每个盘互不相同；这里同尺寸的两个盘叠在一起，
//    搬的时候**永远是一对一对地动**，根本没有「先搬哪一个」的选择。
//    ⇒ 把它们当成两个不同的盘，等于凭空多算了一大堆根本不存在的步骤。
//
// ★ 好消息是：**样例一跑就露馅** —— n = 1 时它输出 3，而答案是 2。
//   这一版真正的教训不是公式记错了，是：**样例是免费的第一道防线，交之前一定跑一遍。**

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    // 2^(2n) − 1：把 2n 个盘当成互不相同的普通汉诺塔
    unsigned long long ans = 1;                 // unsigned：让溢出也是可复现的（见 p1096LL.cpp）
    for (int i = 0; i < 2 * n; i++) ans *= 2;
    cout << ans - 1 << "\n";
    return 0;
}

// 洛谷 P1096 Hanoi 双塔问题 —— 第 ② 版：公式推对了，但 long long 装不下
//
// 输入：n（1 <= n <= 200）
// 输出：最少移动次数
//
// 先把公式推对（题面的提示就是「设法建立 A(n) 与 A(n-1) 的递推关系式」）：
//
//   把 2n 个盘看成 **n 对**，每一对永远一起动。于是它就是一个 n 层的普通汉诺塔，
//   只不过「搬一层」现在要花 2 步（那一对的两个盘各搬一次）。
//
//       A(n) = 2 * A(n-1) + 2          A(1) = 2
//
//   展开就是   A(n) = 2 * (2^n − 1) = 2^(n+1) − 2
//
//   核对样例：n = 1 -> 2^2 − 2 = 2 ✓    n = 2 -> 2^3 − 2 = 6 ✓
//
// ⚠ 公式全对，样例全过，交上去照样 WA —— 因为 n 最大是 **200**：
//     64 位有符号 (long long)     最多撑到 n = 62（2^63 − 2，离上限只差 1）
//     64 位无符号 (unsigned)      最多撑到 n = 63
//     题目要的                    n = 200，答案是一个 **61 位**的数
//   ⚠ 「刚好还塞得进」这种边界最阴 —— 你随手测的 n 很可能全在 62 以内，一路绿灯。
//   ⇒ 和 P1255 数楼梯是同一种失败：**跑得动，但装不下。**
//
// ⚠ 一处刻意的写法：这里用的是 **unsigned long long**。真实的错误是用 long long 写的，
//   但**有符号溢出在 C++ 里是未定义行为**，换个编译器给的数可能就不一样 ——
//   那样这一页里「它输出了什么」就没法当成一个可复现的事实来讲。
//   unsigned 的溢出对 2^64 取模，是有定义的。（第 44 章立的规矩：演示错误也要让错可复现。）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    unsigned long long ans = 1;                 // ⚠ 用 unsigned 见文件头最后一段
    for (int i = 0; i <= n; i++) ans *= 2;      // 2^(n+1)
    cout << ans - 2 << "\n";
    return 0;
}

// 洛谷 P1096 Hanoi 双塔问题 —— 第 ③ 版：公式 + 高精度（正解）
//
// 输入：n（1 <= n <= 200）
// 输出：最少移动次数 A(n) = 2^(n+1) − 2（n = 200 时是一个 61 位的数）
//
// 和第 ② 版的差别只有一处：**把 long long 换成「一个数组存一个大数」**。
// 要做的运算只有两种，都是小学竖式：
//   · 乘 2：逐位乘 2，满十进一（做 n+1 次，就得到 2^(n+1)）
//   · 减 2：从个位减，不够就向上一位借
//
// ⚠ 减 2 之后可能出现**前导零**（比如 100 − 2 = 098），必须把高位的 0 去掉再输出，
//   否则会打出 "098" 这种东西。这道题 n >= 1 时答案至少是 2，不会整个变成 0，
//   但去前导零的循环要留一位保底 —— 养成这个习惯，换道题就用得上。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<int> a{1};                                  // 低位在前；现在表示 1

    for (int t = 0; t <= n; t++) {                     // 乘 2，共 n+1 次 => 2^(n+1)
        int carry = 0;
        for (size_t i = 0; i < a.size(); i++) {
            int s = a[i] * 2 + carry;
            a[i] = s % 10;
            carry = s / 10;
        }
        while (carry) { a.push_back(carry % 10); carry /= 10; }
    }

    a[0] -= 2;                                         // 减 2，从个位开始借位
    for (size_t i = 0; a[i] < 0; i++) { a[i] += 10; a[i + 1] -= 1; }

    while (a.size() > 1 && a.back() == 0) a.pop_back();   // 去前导零，留一位保底

    for (size_t i = a.size(); i-- > 0; ) cout << a[i];
    cout << "\n";
    return 0;
}