24h購物| | PChome| 登入
2011-06-11 08:00:46| 人氣1,014| 回應0 | 上一篇 | 下一篇

d547. 4. 秘密(secrets)

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

http://zerojudge.tw/ShowProblem?problemid=d547

內容 :

傳說 17 世紀著名的海盜船長基德曾將搶來一筆巨額財產藏匿在某無名小島上的洞穴中。因為是筆龐大的財富,所以在他死後,世界各地的寶藏探險家都想找到他寶藏的藏匿 之處。但傳說因為基德船長怨靈的詛咒,進入洞穴的人都難逃一死,至今還沒有人活著出來過!因為恐懼,慢慢的大家不再提起這批寶藏,而寶藏的謎一直延續到現 在。

傑克船長是一知名的寶藏探險家,至今已經找到許多傳說中藏匿的寶藏。某一天,傑克在酒吧裡因緣際會地得到這筆寶藏的藏寶圖,藏寶圖上 除了揭露寶藏的所在地外還有一串由 0 與 1 組成的奇怪數字串。傑克船長於是根據藏寶圖率領他的船員順利地找到這無名的小島並進入洞穴中,最後抵達寶藏藏匿的地點。但他們卻發現藏匿寶藏的地點有無數 道門,而每一扇門上都有一串奇怪的數列(包含 0 與 1 以外的其他整數值,整數之間有空格間隔)。而從白骨遍地的情景來推斷,這些門之中可能只有一扇門中有真正的寶藏,只有找對那扇門才能順利取得寶藏;而若開 錯門,可能會引來殺身之禍!

傑克船長幾經推敲,終於發現門上的數列跟藏寶圖上的 0、1 數字串有某種關連,於是他將解法教給他的船員,要他們找出正確的門是哪一扇門。聰明的你(妳),請幫助傑克船長的船員,寫一組程式算出看看哪一扇門後才是真正藏有寶藏,使他們能順利地取得寶藏!

例如,有 3 扇門,門上的數字串如下:       藏寶圖上提示密碼為:
27 13 45 57 30                                0 1 0 1
3 7 21 30 81
20 42 61 123 145

解法過程

  1. 先解第一扇門的數字串 27 13 45 57 30
  2. 由後往前(即右往左)推算,最後兩個數字先比大小,後面大於等於前面則為 1,反之為 0
  3. 30 < 57→ 0
  4. 接著後兩個數字相減的值取絕對值跟第三個數字比大小,若大於等於第三個數字為 1,反之為 0
  5. 30–57 = -27,取絕對值為 27 < 45 → 0
  6. 以此類推,若前面已無數字可比,則結束
  7. 57–45 = 12 < 13 → 0
  8. 45–13 = 32 > 27 → 1
  9. 所以 27 13 45 57 30 對應的 0、1 數字串為 1 0 0 0
  10. 同樣推算出第二串與第三串數字對應的 0、1 數字串
  11. 3 7 21 30 81 → 1 1 1 1
  12. 20 42 61 123 145 → 0 1 0 1
  13. 三扇門的數字串中唯一與提示密碼 0 1 0 1 符合者為 20 42 61 123 145,則此一扇門後即是真正藏有寶藏

 

輸入說明 :

輸入檔案中的第一行為兩正整數 N 與 M 其中 N 表示門的個數,M 代表地圖上的 0、1 數字串的個數

第二行為一串由 0、1 組成的數字串,以空格隔開,為提示密碼。

接著有 N 行,每一行對應某一扇門的數字串、數字間一樣以空格隔開,這 N 行中有一行的數字串為正確解答。

輸出說明 :

 輸出正確解答的數字串,以空格隔開。

範例輸入 :

2 2	
0 0
3 5 4
12 45 47

範例輸出 :

3 5 4

提示 :

出處 :

北市 98 資訊學科能力競賽 (管理:example)



作法 : 模擬

/**********************************************************************************/
/*  Problem: d547 "4. 秘密(secrets)" from 北市 98 資訊學科能力競賽    */
/*  Language: C                                                                   */
/*  Result: AC (2ms, 294KB) on ZeroJudge                                          */
/*  Author: morris1028 at 2011-06-11 07:38:50                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
main() {
    int n, m;
    while(scanf("%d %d", &n, &m) == 2) {
        int ans[100], a, b;
        int data[100][100];
        for(a = 0; a < m; a++)
            scanf("%d", &ans[a]);
        for(a = 0; a < n; a++) {
            for(b = 0; b <= m; b++)
                scanf("%d", &data[a][b]);
        }
        for(a = 0; a < n; a++) {
            int t = {data[a][m]}, flag = 0;
            for(b = m-1; b >= 0; b--) {
                if(t >= data[a][b]) {
                    if(ans[b] != 1) {flag = 1;}
                }
                else {
                    if(ans[b] != 0) {flag = 1;}
                }
                t = abs(data[a][b+1] - data[a][b]);
            }
            if(flag == 0) {
                for(b = 0; b <= m; b++)
                    printf("%d ", data[a][b]);
                puts("");break;
            }
        }
    }
    return 0;
}

台長: Morris
人氣(1,014) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:d887. 1.山脈種類(chain)
此分類上一篇:d548. 5. 購物網站(web)

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文