IOI2009中国国家队选拔赛 Day1.pdf

IOI2009 中国国家队选拔赛 第一试 2009-05-05 IOI2009 中国国家队选拔赛 CTSC 2009 Day1 竞赛时间：2009 年5 月5 日上午8:00-13:00 题目名称 移盘子 移民站选址 序列变换 目录 trique locate sequence 可执行文件名 trique N/A sequence 输入文件名 trique.in locate 1.in ~ sequence.in locate 10.in 输出文件名 trique.out locate 1.out ~ sequence.out locate 10.out 每个测试点时限 3 秒 N/A 3 秒 测试点数目 10 10 10 每个测试点分值 10 10 10 是否有部分分 无 有 无 题目类型 传统 提交答案 传统 附加文件 无 checker 无 提交源程序须加后缀 对于Pascal 语言 trique.pas N/A sequence.pas 对于C 语言 trique.c N/A sequence.c 对于C++ 语言 trique.cpp N/A sequence.cpp 注意：最终测试时，所有编译命令均不打开任何优化开关 第1 页 共7 页 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