POJ1029 False coin

题目大意：

　　与1013有一些相似之处。有N枚硬币，其中有一枚假币，重量与别的不同。现有一个精准天平。为了找出假币，我们把所有硬币编号1到N。每次在天平两端放等数目的硬币进行称量。每次称量的结果都被记录下来。写一个程序来找出那没假币。

输入：第一行中，第一个数N(2<=N<=1000)表示有多少枚硬币，第二个数K(1<=K<=100)表示称了多少次。接下来有2K行，每两行中的前一行第一个数为天平每端硬币枚数，后面为天平两端的硬币编号，后一行用一个符号表示天平的称量结果：

'<':左边轻　　'>':左边重　　 '=':两边一样重

输出：找到的假币编号。若找不到，输出0.

Sample Input

Sample Output

开始用1013的方法做，测试的时候出现各种问题，最后发现直接暴力就能过了..

枚举每枚硬币是假币（重、轻两种情况）的假设，与称量结果相符表示可行，矛盾表示不可行。

  1 //////////////////////////////////////////////////////////////////////////
  2 //        POJ1029 False coin
  3 //        Memory: 676K        Time: 63MS
  4 //        Language: C++        Result: Accepted
  5 //////////////////////////////////////////////////////////////////////////
  6 
  7 #include <iostream>
  8 
  9 using namespace std;
 10 
 11 int main() {
 12     int N;
 13     int k;
 14     cin >> N;
 15     int f[1001];
 16     for (int i = 1; i <= N; ++i) {
 17         f[i] = 0;
 18     }
 19     cin >> k;
 20     int temp[100][1000];
 21     int pi[100];
 22     char sign[100];
 23     int i;
 24     for (i = 0; i < k; ++i) {
 25         cin >> pi[i];
 26         for (int j = 0; j < 2 * pi[i]; ++j) {
 27             cin >> temp[i][j];
 28         }
 29         cin >> sign[i];
 30     }
 31     for (int i = 1; i <= N; ++i) {
 32         //假设i为重
 33         for (int j = 0; j < k; ++j) {
 34             int t;
 35             bool flag;
 36             if (sign[j] == '=') {
 37                 for (int t = 0; t < 2 * pi[j]; ++t) {
 38                     if (temp[j][t] == i) {
 39                         f[i] = 1;
 40                         break;
 41                     }
 42                 }
 43             } else if (sign[j] == '>') {
 44                 flag = false;
 45                 for (t = 0; t < pi[j]; ++t) {
 46                     if (temp[j][t] == i) {
 47                         flag = true;
 48                         break;
 49                     }
 50                 }
 51                 if (flag == false) {
 52                     f[i] = 1;
 53                 }
 54             } else if (sign[j] == '<') {
 55                 flag = false;
 56                 for (t = pi[j]; t < 2 * pi[j]; ++t) {
 57                     if (temp[j][t] == i) {
 58                         flag = true;
 59                         break;
 60                     }
 61                 }
 62                 if (flag == false) {
 63                     f[i] = 1;
 64                 }
 65             }
 66         }
 67         if (f[i] != 1) {
 68             f[i] = 2;
 69         }
 70         //假设i为轻
 71         if (f[i] == 2) {
 72             continue;
 73         }
 74         for (int j = 0; j < k; ++j) {
 75             int t;
 76             bool flag;
 77             if (sign[j] == '=') {
 78                 for (int t = 0; t < 2 * pi[j]; ++t) {
 79                     if (temp[j][t] == i) {
 80                         f[i] = -1;
 81                         break;
 82                     }
 83                 }
 84             } else if (sign[j] == '<') {
 85                 flag = false;
 86                 for (t = 0; t < pi[j]; ++t) {
 87                     if (temp[j][t] == i) {
 88                         flag = true;
 89                         break;
 90                     }
 91                 }
 92                 if (flag == false) {
 93                     f[i] = -1;
 94                 }
 95             } else if (sign[j] == '>') {
 96                 flag = false;
 97                 for (t = pi[j]; t < 2 * pi[j]; ++t) {
 98                     if (temp[j][t] == i) {
 99                         flag = true;
100                         break;
101                     }
102                 }
103                 if (flag == false) {
104                     f[i] = -1;
105                 }
106             }
107         }
108         if (f[i] != -1) {
109             f[i] = -2;
110         }
111     }
112     int res;
113     int zres;
114     int cnt = 0;
115     int zcnt = 0;
116     for (i = 1; i <= N; ++i) {
117         if (f[i] == 2 || f[i] == -2) {
118             ++cnt;
119             res = i;
120         } else if (f[i]  == 0) {
121             ++zcnt;
122             zres = i;
123         }    
124     }
125     if (cnt > 1) {
126         cout << 0;
127     } else if (cnt == 1) {
128         cout << res;
129     } else if (cnt == 0 && zcnt == 1) {
130         cout << zres;
131     } else {
132         cout << 0;
133     }
134     system("pause");
135     return 0;
136 }

View Code