a206. 學長的鬼腳圖 (二)＠Morris' Blog｜PChome Online 個人新聞台

2011-08-09 08:30:20| 人氣1,261| 回應0 | 上一篇 | 下一篇

a206. 學長的鬼腳圖 (二)

推薦 0 收藏 0 轉貼0 訂閱站台

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.

提示：

背景知識： 0-1原理並行排序 sorting network

您應該注意的是

如果一個比較網絡是

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筆資料

出處：

學長的鬼腳圖 GrD改編 (管理：grd)

作法 : 純模擬

/**********************************************************************************/
/* 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;
}

我要檢舉

#a206#學長的鬼腳圖 (二)

台長： Morris

您可能對以下文章有興趣

[a462] Beats of the Angel

[ZJ][離線、BIT、離散化] a580. 輻射擴散

[ZJ][單調堆] a813 2013高雄市能力競賽高中組 4. 城市觀測

[ZJ][2DST][zkw] d800. ST版区间MAX

人氣(1,261) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:a207. 精準覆蓋問題(Exact cover)
此分類上一篇:a202. 學長的鬼腳圖

回應(0)