2011-06-30 18:11:47Morris
c095. False coin
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。
範例輸入 ：
25 32 1 2 3 4<1 1 4=1 2 5=4 21 1 2<1 3 4=
範例輸出 ：
30
提示 ：
出處 ：
ACM 665
作法 : 窮舉
窮舉錯誤的那個硬幣，然後看所有條件有沒有都符合
給的條件，若是"="，則出現的硬幣，皆不可能是錯誤的，不必窮舉
找不到，或者出現兩個以上的錯誤硬幣，則輸出 0
作法 : 窮舉
窮舉錯誤的那個硬幣，然後看所有條件有沒有都符合
給的條件，若是"="，則出現的硬幣，皆不可能是錯誤的，不必窮舉
找不到，或者出現兩個以上的錯誤硬幣，則輸出 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;
}