24h購物| | PChome| 登入
2011-06-30 18:11:47| 人氣1,666| 回應0 | 上一篇 | 下一篇

c095. False coin

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

c095. False coin

內容 :

「金條」銀行根據可靠消息,他們的最後一批(有N個)硬幣裡有一個是假的,而且它的重量和真的不同(每個真的硬幣都一樣重)。在金融危機之後,他們只剩下如上圖的天平。那個天平能用來確定左邊盤子裡的東西比右邊的重、輕、還是一樣。

為了找出假幣,銀行職員把所有的硬幣編號(從 1 到 N ),然後他們就開始秤重了。他們每次都把左右放一樣多的硬幣,然後記錄硬幣的編號以及秤重結果。

你要寫一個程式幫他們找出假的硬幣。

 

輸入說明 :

輸入的第一列有一個整數 M,代表以下有幾組測試資料。

每組測試資料的第一列有2個整數 N 和 K。N 代表硬幣的數量(1 <= N <= 100),K 是秤重的次數(1 <= K <= 100)。接下來的 2K 列描述秤重,每連續的2列是一次秤重。前一列開始有一個數Pi(1 <= Pi <= N/2),代表這次秤重每邊放的硬幣個數,接下來的前 Pi個數字是左邊的硬幣號碼,後 Pi 個數字是右邊的硬幣號碼。後一列用 <, >, 或 = 表示秤重的結果。

  • < 表示左邊比右邊的輕
  • > 表示左邊比右邊的重
  • = 表示兩邊一樣重

輸入的第一列與第一組測試資料,以及各組測試資料間均有一空白列。請參考Sample Input。

輸出說明 :

對每一組測試資料輸出哪一個硬幣是假的。如果秤重的結果無法找出假幣,請輸出 0。

測試資料間亦請輸出一空白列,請參考Sample Output。

範例輸入 :help

25 32 1 2 3 4<1 1 4=1 2 5=4 21 1 2<1 3 4=

範例輸出 :

30

提示 :

* 中文翻譯:Lucky 貓

出處 :

ACM 665



作法 : 窮舉
窮舉錯誤的那個硬幣,然後看所有條件有沒有都符合
給的條件,若是"=",則出現的硬幣,皆不可能是錯誤的,不必窮舉
找不到,或者出現兩個以上的錯誤硬幣,則輸出 0


#include<stdio.h>
struct record {
    int l[101], r[101];
    char st[2];
}D[100];
main() {
    int m, n, k, a, b, c, pi, x;
    scanf("%d", &m);
    while(m--) {
        scanf("%d %d", &n, &k);
        int possible[101] = {};
        for(a = 0; a < k; a++) {
            for(b = 1; b <= n; b++) {
                D[a].l[b] = D[a].r[b] = 0;
            }
        }
        for(a = 0; a < k; a++) {
            scanf("%d", &pi);
            for(b = 0; b < pi; b++)    scanf("%d", &x), D[a].l[x] = 1;
            for(b = 0; b < pi; b++)    scanf("%d", &x), D[a].r[x] = 1;
            scanf("%s", &D[a].st);
            if(D[a].st[0] == '=') {
                for(b = 1; b <= n; b++) {
                    if(D[a].l[b])    possible[b] = 1;
                    if(D[a].r[b])    possible[b] = 1;
                }
            }
        }
        int Ans = 0, flag = 0, ll, lr, hl, hr;
        for(a = 1; a <= n; a++) {
            if(possible[a]) continue;
            for(b = 0; b < k; b++) {
                ll = lr = hl = hr = 0;
                if(D[b].l[a] != 0) ll--;
                if(D[b].r[a] != 0) lr--;
                if(D[b].l[a] != 0) hl++;
                if(D[b].r[a] != 0) hr++;
                if(ll == lr && D[b].st[0] == '=') continue;
                if(ll < lr && D[b].st[0] == '<') continue;
                if(ll > lr && D[b].st[0] == '>') continue;
                if(hl == hr && D[b].st[0] == '=') continue;
                if(hl < hr && D[b].st[0] == '<') continue;
                if(hl > hr && D[b].st[0] == '>') continue;
                break;
            }
            if(b == k)
                flag++, Ans = a;
        }
        if(flag == 1)    printf("%d\n", Ans);
        else puts("0");
        if(m)    puts("");
    }
    return 0;

台長: Morris
人氣(1,666) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:a159. 11743 - Credit Check
此分類上一篇:c093. Counterfeit Dollar

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