#PQJ102x6685. QOJ 102_6685
QOJ 102_6685
IOI2009 中国国家队选拔赛 第一试 2009-05-05 移盘子 【问题描述】 已知有三根柱子,分别记为A,B 和C。初始状态时A 上放有N 个盘子,而 B 和C 两个柱子上没有放任何盘子。你每次能做的移动操作就是把某根柱子最上 面的一个盘子拿下来,然后放到另一个柱子上。盘子有三类,分别用1,2,3 来表示。你的目标是,让所有1 类盘子最终放在A 上,让所有2 类盘子最终放 在B 上,所有3 类盘子最终放在C 上。现在让你求出实现上述目标总共最少需 要多少次移动? 【输入文件】 输入文件trique.in 第一行包含一个整数N,为盘子的总数。 第二行有N 个数,每个数只能是1,2,3 之一。这N 个数表示在初始状态时 第一个柱子上所有盘子的类型,按照从上往下的顺序。 【输出文件】 输出文件trique.out 只包含一个数,即最少的移动次数。 【样例输入】 5 1 2 1 3 3 【样例输出】 8 【样例说明】 初始状态如下图: A B C 1 2 1 3 3 第2 页 共7 页 IOI2009 中国国家队选拔赛 第一试 2009-05-05 第几次移动 被移动的盘子 从第几根柱子 到第几根柱子 1 1 A C 2 2 A B 3 1 A B 4 1 C B 5 3 A C 6 3 A C 7 1 B A 8 1 B A 【数据规模】 对于20%的数据,盘子的种类不超过2 种; 对于40%的数据,N ≤ 300; 对于100%的数据,N ≤ 1000。 第3 页 共7 页