a206: 學長的鬼腳圖 (二)
Tags : 0-1原理 sorting network 並行排序
Accepted rate : 29人/29人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-12 22:42

Content

改編自:A202 學長的鬼腳圖

 

學長的鬼腳圖,經過擦擦塗塗修修改改後

竟然也可以排序了 !?!?!

 

9─┬──┬─────1
3─┴──┼─┬─┬─3
7──┬─┴─┼─┴─7
1──┴───┴───9     (一個可靠的排序網絡)

沒錯,鬼腳圖搖身一變變成了可靠的排序方式,叫做"並行排序"

這是一個由許多比較器所組成的比較網絡(範例為4輸入4輸出),而他是一個可靠的排序網絡 (比較網絡中的排序網絡)

一個可靠排序網絡的工作方式


─9─┬──┬─────         ─9─┬─3─┬─────
─3─┴──┼─┬─┬─         ─3─┴─9─┼─┬─┬─
─7──┬─┴─┼─┴─         ─7──┬1─┴─┼─┴─
─1──┴───┴─── (a)    ─1──┴7───┴─── (b)


─9─┬─3─┬──1───      ─9─┬─3─┬──1───1
─3─┴─9─┼─┬7─┬─      ─3─┴─9─┼─┬7─┬─3
─7──┬1─┴─┼3─┴─      ─7──┬1─┴─┼3─┴─7
─1──┴7───┴9───(c)  ─1──┴7───┴9───9(d)

經過4個比較之後,網絡輸出端即會輸出正確的遞增排序數字出來~~

下面是一個插入排序的排序網絡

a1 ─┬───┬───┬───┬───┬───┬───┬─ b1
a2 ─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─ b2
a3 ───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─── b3
a4 ─────┴─┬─┴─┬─┴─┬─┴─┬─┴───── b4
a5 ───────┴─┬─┴─┬─┴─┬─┴─────── b5
a6 ─────────┴─┬─┴─┬─┴───────── b6
a7 ───────────┴─┬─┴─────────── b7
a8 ─────────────┴───────────── b8

 

沒錯~

這次希望你可以來判定,經過擦擦塗塗修修改改的鬼腳圖到底是不是可靠的排序網絡呢?

Input
第一行為n,m   n(0<n<=64)代表這個比較網絡有幾個輸入,m(0<m<=256)代表長度
第二行有一個數字x(0<x<=1000),代表測試排序的數字有幾組,你可以相信如果是一個不可靠的排序網絡,這個表現會在測試數組中出現
接下來x行為n個輸入的數字 (0<=An<=2147483647)
之後為排序網絡輸入
 
測資間沒有空行,以eof結尾 
Output

如果是一個可靠的排序網絡的話

請輸出 "This is a reliable sorting ghost leg!"

如果不是一個可靠的排序網路的話

請輸出 "So sad......This is just a  ghost leg."

Sample Input
4 12
1
0 1 1 0
-A--C-------
-A--C-D--E--
---BC-D--E--
---B--D-----
8 27 
1
1 0 1 1 5 1 4 3
-A---H---N---S---X---A---C-
-A-B-H-I-N-O-S-T-X-Y-A-B-C-
---B-C-I-J-O-P-T-U-Y-Z-B---
-----C-D-J-K-P-Q-U-W-Z-----
-------D-E-K-L-Q-R-W-------
---------E-F-L-M-R---------
-----------F-G-M-----------
-------------G-------------
8 14
1
0 0 1 1 0 1 1 1
--A-----------
--A--B--------
--A--B--C-----
--A--B--C--D--
--A--B--C--D--
-----B--C--D--
--------C--D--
-----------D--
Sample Output
This is a reliable sorting ghost leg!
This is a reliable sorting ghost leg!
So sad......This is just a  ghost leg.
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (1%): 1.0s , <1K
公開 測資點#1 (1%): 1.0s , <1M
公開 測資點#2 (1%): 1.0s , <1M
公開 測資點#3 (30%): 1.0s , <1M
公開 測資點#4 (7%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (37%): 1.0s , <1M
公開 測資點#7 (13%): 1.0s , <1M
Hint :

您應該注意的是

如果一個比較網絡是

a1  --A-----C--
a2  --A--B-C---
a3  --A--B----- 

這代表對於A比較器 您應該比較a1跟a3

對於B比較器 您應該比較 a2跟a3

對於C比較器 您應該比較 a1跟a2

 

而比較器編號只會在A~Z之間

但是不代表每個英文字母只會出現一次

但是保證相同的字母不會出現在旁邊,避免搞混

 

感謝morris1028 , liouzhou_101 和 stanley17112000 通知

2011/08/05 16:24 修正測資 , 重測6筆資料

2011/08/05 20:55 加強測資 , 重測7筆資料

2011/08/06 00:29 修正測資 , 重測7筆資料

Tags:
0-1原理 sorting network 並行排序
出處:
學長的鬼腳圖 GrD改編 [管理者:
grd (保持好奇心)
]


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