d730: 升旗典礼 ——加强版
Tags :
Accepted rate : 32人/34人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-06-16 20:06

Content

幼稚園老師帶小朋友最頭痛的就是在昇旗典禮的時候。

小朋友在典禮中很容易亂動,要令他們都朝向旗子所在的方向卻是困難的。

現在簡化問題。總共有9個小朋友,小朋友面朝的方向只有北東南西四個方向。

我們定義0為北方, 1為東方, 2為南方, 3為西方, 從北方開始, 順時針方向轉一圈為0 -> 1 -> 2 -> 3 -> 0。

老師則使用9種口令來同時讓數位小朋友順時針轉90度

口令   那幾個小朋友順時針轉90度(數字代表第幾個)

1    1, 2, 4, 5

2    1, 2, 3

3    2, 3, 5, 6

4    1, 4, 7

5    2, 4, 5, 6, 8

6    3, 6, 9

7    4, 5, 7, 8 

8    7, 8, 9

9    5, 6, 8, 9

 

例如:如果原本第1, 2, 4, 5個小朋友面朝北方(0),老師喊口令1,第1, 2, 4, 5個小朋友會變成面朝東方(1)

旗子永遠在北方,而老師要使用口令讓所有小朋友都朝向北方。口令使用次數不限,請你求出其一連串的口令所形成的最短序列,並列印出來。

Input

输入包含许多组测资。

测资第一行有一个整数,代表共有几组测资。

每组测资为1行,这一行里有9个整数,范围0到3,代表9位小朋友原本所朝的方向。

这9个整数的每个整数之间以一个空白字元隔开。

 

Output

输出为口令所形成的最短序列,每组输出为1行,其口令序列中的每个口令间以一个空白字元隔开。

如果有2组(含)以上的最短序列,请输出字典排序最小者。

例如:1 1 3 4 5 和1 2 3 4 5 两序列,要输出1 1 3 4 5。

Sample Input
1
2 3 1 1 1 3 0 0 0
Sample Output
1 1 2 2 2 4 8 8 8 9
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <10M
Hint :

 这题是 d298: 升旗典礼 加强版。

测试数据可能会非常庞大,所以你的程序一定要跑得非常快。//一共大约100000笔

为这题抓狂吧!

Tags:
出處:
IOI1994The Clocks 再次加强 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」