#P4072. [Wf2014]baggage

    ID: 1779 传统题 1000ms 128MiB 尝试: 37 已通过: 19 难度: 8 上传者: 标签>CF2400提高+/省选-递归构造势能分析鸣谢wangtianyi1998提供SPJ及题面

[Wf2014]baggage

题目描述

给定一排长度为 4n4n 的格子,编号从 −2n+1-2n+1 到 2n2n。

每个编号为正的格子中有一个物品,其中每个编号为奇数的格子中有一个 BB 类物品,编号为偶数的格子中有一个 AA 类物品。

例如,当 n=4n=4 时初始状态如下图所示:

你只能进行一种操作:选择某两个都有物品的相邻的格子,然后移动到另外两个相邻的空格子中,不能改变两个格子的相对位置。

要求进行最少的操作使得所有物品以 AAA...ABBB...BAAA...ABBB...B (nn 个 AA 和 nn 个 BB )的形式排列在一起。

输入格式

输入数据包含一行一个正整数 nn ,含义如题面中所示。

输出格式

输出一个最短的满足要求的移动序列。

每个操作的格式如下:x to y

含义为将 xx 和 x+1x+1 两个格子中的物品移动到 yy 和 y+1y+1 两个位置。

如果有多组方案可以达到要求,你可以输出任意一组。

5
8 to -1
3 to 8
6 to 3
0 to 6
9 to 0

数据规模与约定

对于 100%100\% 的数据满足,3≤n≤1003 \leq n \leq 100。