Skip to content

11384: 【原1384】Hanoi

题目

题目描述

author: greatwall1995 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1384

Description

最近,小L突然对汉诺塔非常感兴趣。在研究了最原始的汉诺塔问题(最少需要移动多少步才能将第一根轴上的n个圆盘移到第三根轴上)之后,小L开始想:如果n个圆盘初始时不全在第一根轴上,最少需要移动多少步才能将它们移到第三根轴。请你帮助他解决这个问题。

Input Format

第一行一个整数n表示圆盘的个数。

第二行有n个数,其中第i个数a_i表示第i小的圆盘初始时在第a_i根轴上。(1≤a_i≤3)

对于10%的数据,1≤n≤2

对于30%的数据,1≤n≤5

对于50%的数据,1≤n≤12

对于80%的数据,1≤n≤1,000

对于100%的数据,1≤n≤1,000,000

Output Format

一个整数表示答案。

Sample Input

3
1 1 1

Sample Output

7

Hint

什么是汉诺塔?

汉诺塔由3根轴和若干个大小各不相同,套在这3根轴的圆盘组成。每个圆盘必须比叠在它上方的圆盘大。每次移动时,可以选取某根轴上最上方的圆盘移到另一根轴上,但移动后仍然要维持汉诺塔本身的要求。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!