logo AlgoBeat OnlineJudge
登录 注册

#215927. [蓝桥杯第二届国际赛] 汉诺塔问题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

汉诺塔问题是一个经典的数学问题。

给定三根柱子 A、B、C,柱子 A 上按大小顺序放着 个大小不同的盘子,最下面的盘子最大,最上面的盘子最小。现在要将所有盘子从柱子 A 移动到柱子 C 中,问最少要移动多少次。

答案是最少 次。而且要以最少的次数完成移动,只存在一种方案。

比如,当 时,总共要移动 步:

步:最小的盘子中 A 移到 C,记为 A->C;

步:第 小的盘子从 A 移到 B,记为 A->B;

步:最小的盘子中 C 移到 B,记为 C->B;

步:第 小的盘子从 A 移到 C,记为 A->C;

步:最小的盘子中 B 移到 A,记为 B->A;

步:第 小的盘子从 B 移到 C,记为 B->C;

步:最小的盘子中 A 移到 C,记为 A->C。

请问,在第 步到第 步之间,有多少次 A->B,多少次 A->C,多少次 B->A,多少次 B->C,多少次 C->A,多少次 C->B?

输入格式

输入的第一行包含一个整数

第二行包含两个整数 ,用一个空格分隔。

输出格式

输出六行,每行一个整数。分别表示以上六个问题的答案。

样例

样例输入 1

3
2 6

样例输出 1

1
1
1
1
0
1

数据范围与提示

【数据规模与约定】

对于 的评测用例,

对于 的评测用例,

对于所有评测用例,