d298: 昇旗典禮
Tags :
Accepted rate : 40人/41人 ( 98% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 02:03

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%): 1.0s , <1K
Hint :
Tags:
出處:
IOI1994改編 [管理者:
bleed1979 (Bleed)
]


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