| 比赛场次 | 118 |
|---|---|
| 比赛名称 | 20120217 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2012-02-17 19:00:00 |
| 结束时间 | 2012-02-17 22:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 |
| 题目名称 | 分球 |
|---|---|
| 输入输出 | balls.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试点数 | 8 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 Citron酱 |
WWWWWWEE | 0.000 s | 0.00 MiB | 0 |
 Launcher |
WWWWWWWW | 0.000 s | 0.00 MiB | 0 |
 苏轼 |
WWWWWWWW | 0.000 s | 0.00 MiB | 0 |
 Makazeu |
RRRRRRRR | 0.000 s | 0.00 MiB | 0 |
 Truth.Cirno |
WWWWTTTT | 0.000 s | 0.00 MiB | 0 |
 皪林展也 |
WWWWWWWW | 0.000 s | 0.00 MiB | 0 |
 Yeehok |
WWWWWWWW | 0.000 s | 0.00 MiB | 0 |
 王者自由 |
C | 0.000 s | 0.00 MiB | 0 |
【问题描述】
在一个装满财宝的屋子里，有2N个盒子排成一排。除了两个相邻的空盒外，其余的每个盒子里都装有一个金球或者一个银球，总共有N-1个金球和N-1个银球。用图6．3所示为一个N=5时的例子，G表示金球，S表示银球。
|
G
|
S
|
S
|
G
|
|
|
G
|
S
|
G
|
S
|
任意两个相邻的非空的盒子里的球可以移动到两个相邻的空盒中，移动不能改变这两个球的排列顺序。写一个程序，用最少的移动次数把所有的金球都移到所有的银球的左边。
【输入格式】
输入文件包含多组数据。第一行为K，表示数据的总数。
每组数据的第一行是N(3≤N≤7)，
第二行是2N个盒子的初始状态。金球用a表示， 银球用b表示，空盒用空格表示。每两组相邻数据用空行隔开。
【输出格式】
对于每一组数据，若无解则输出一行NO SOLUTION，若有解，输出一组状态来表示移动的序列，每个状态占一行。每行输出到此状态的移动的步数，紧接着是一个空格，然后是此时的状态。初始状态为第0步，每组数据都要先输出初始状态。如有多种最少移动次数的方案，输出“空格靠前靠左”的一种，如下两种方案，需输出第二种。
0 bbbb aaaa
1 bbbbaa aa
2 bbaabbaa
3 aabbaabb
4 aa aabbbb
1 bbbbaa aa
2 bbaabbaa
3 aabbaabb
4 aa aabbbb
0 bbbb aaaa
1 bbbbaaaa
2 aabbbb aa
3 aa bbbbaa
4 aaaabbbb
1 bbbbaaaa
2 aabbbb aa
3 aa bbbbaa
4 aaaabbbb
相邻的两组数据用一个空行隔开。
【输入输出样例】
样例输入（balls.in）:
3 3 abab 5 abba abab 6 a babbababa
样例输出（balls.out）：
NO SOLUTION 0 abba abab 1 abbabaa b 2 a abaabbb 3 aaaab bbb 0 a babbababa 1 aabbabb aba 2 aabbabbbaa 3 aa abbbaabb 4 aaaaabbb bb