a206. 學長的鬼腳圖 (二)
內容 ：
改編自: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
沒錯~
這次希望你可以來判定,經過擦擦塗塗修修改改的鬼腳圖到底是不是可靠的排序網絡呢?
輸入說明
：
第一行為n,m n(0<n<=64)代表這個比較網絡有幾個輸入,m(0<m<=256)代表長度
第二行有一個數字x(0<x<=1000),代表測試排序的數字有幾組,你可以相信如果是一個不可靠的排序網絡,這個表現會在測試數組中出現
接下來x行為n個輸入的數字 (0<=An<=2147483647)
之後為排序網絡輸入
測資間沒有空行,以eof結尾
輸出說明
：
如果是一個可靠的排序網絡的話
請輸出 "This is a reliable sorting ghost leg!"
如果不是一個可靠的排序網路的話
請輸出 "So sad......This is just a ghost leg."
範例輸入 ：
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--
範例輸出 ：
This is a reliable sorting ghost leg! This is a reliable sorting ghost leg! So sad......This is just a ghost leg.
提示
：
您應該注意的是
如果一個比較網絡是
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筆資料
出處
：
/**********************************************************************************/
/* Problem: a206 "學長的鬼腳圖 (二)" from 學長的鬼腳圖 GrD改編 */
/* Language: C */
/* Result: AC (8ms, 407KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-09 08:28:40 */
/**********************************************************************************/
#include<stdio.h>
main() {
int n, m, t, a, b, c, temp;
int test[1000][65], t2[65];
char map[65][257];
for(a = 0; a < 257; a++) map[0][a] = '-';
while(scanf("%d %d", &n, &m) == 2) {
scanf("%d", &t);
for(a = 0; a < t; a++)
for(b = 1; b <= n; b++)
scanf("%d", &test[a][b]);
for(a = 1, getchar(); a <= n; a++) gets(map[a]);
int flag = 1, tmp, u;
for(a = 0; a < t; a++) {
for(b = 0; b < m; b++, c = 1) {
while(c <= n) {
while(map[c][b] == '-' && c <= n) c++;
u = c, c++;
while(map[c][b] == map[c-1][b] && c <= n) c++;
if(test[a][u] > test[a][c-1]) tmp = test[a][u], test[a][u] = test[a][c-1], test[a][c-1] = tmp;
while(map[c][b] == '-' && c <= n) c++;
}
}
for(c = 2; c <= n && flag; c++)
if(test[a][c] < test[a][c-1])
flag = 0;
}
if(flag) puts("This is a reliable sorting ghost leg!");
else puts("So sad......This is just a ghost leg.");
}
return 0;
}