冠军魔术（C语言二级 · 编程题）

**时间限制：**1000 ms **内存限制：**65535 KB **分值：**20 分（建议）

---

题目描述

2018 年 FISM（世界魔术大会）近景总冠军简纶廷的表演中有一个情节：以桌面上一根带子为界，当他将纸牌从带子的一边推到另一边时，纸牌会变成硬币；把硬币推回另一边会变成纸牌。 设定规则如下：

• 纸牌 → 推到另一边后，变成等量的硬币；
• 硬币 → 推回另一边后，变成数量加倍的纸牌。

给定纸牌的​初始数量​，当他来回推了 N 次（“去”或“回”都算一次）后，问：手里拿的是纸牌还是硬币？数量是多少？ 初始状态手里全是纸牌。

---

输入格式

一行两个正整数：A N

• A 为初始纸牌数量
• N 为推送次数（来/回各记一次）

---

输出格式

若最后手里是纸牌，输出：0 数量 若最后手里是硬币，输出：1 数量 两数之间用一个空格隔开。题目保证结果不超过 2³¹−1。

---

样例

样例输入 1

3 7

样例输出 1

1 24

样例输入 2

8 4

样例输出 2

0 32

---

题目分析与解法

设初始纸牌数为 A。每次跨带子推送的转换为：

• 若当前是纸牌：推送后变为等量硬币（数量不变）；
• 若当前是硬币：推送后变为纸牌且数量​翻倍​。

从状态序列看：

• 第 1 次（奇数次）：纸牌 → 硬币，数量为 A
• 第 2 次（偶数次）：硬币 → 纸牌，数量为 2A
• 第 3 次：纸币 → 硬币，数量为 2A
• 第 4 次：硬币 → 纸牌，数量为 4A
• …

可见每完成两次推送，纸牌数量会​翻倍一次​。因此有闭式结论：

• 若 N 为偶数：最终为​纸牌​，数量 A * 2^(N/2)
• 若 N 为奇数：最终为​硬币​，数量 A * 2^((N-1)/2)

实现时只需根据奇偶计算相应的 2 的幂并乘以 A。题目保证结果不溢出 32 位有符号整型。

---

边界说明

• N = 0：未推送，仍为纸牌，输出 0 A
• A ≥ 1，N ≥ 0，且 A * 2^⌊N/2⌋ ≤ 2^31−1（由题面保证）

---

复杂度分析

仅进行幂次计算和常数运算，时间复杂度 O(1)，空间复杂度 O(1)。

---