# POJ 1029 False coin C++版

POJ题解 2750浏览

Description

The “Gold Bar”bank received information from reliable sources that in their last group of N coins exactly one coin is false and differs in weight from other coins (while all other coins are equal in weight). After the economic crisis they have only a simple balance available (like one in the picture). Using this balance, one is able to determine if the weight of objects in the left pan is less than, greater than, or equal to the weight of objects in the right pan.
In order to detect the false coin the bank employees numbered all coins by the integers from 1 to N, thus assigning each coin a unique integer identifier. After that they began to weight various groups of coins by placing equal numbers of coins in the left pan and in the right pan. The identifiers of coins and the results of the weightings were carefully recorded.
You are to write a program that will help the bank employees to determine the identifier of the false coin using the results of these weightings.

Input

The first line of the input file contains two integers N and K, separated by spaces, where N is the number of coins (2<=N<=1000 ) and K is the number of weightings fulfilled (1<=K<=100). The following 2K lines describe all weightings. Two consecutive lines describe each weighting. The first of them starts with a number Pi (1<=Pi<=N/2), representing the number of coins placed in the left and in the right pans, followed by Pi identifiers of coins placed in the left pan and Pi identifiers of coins placed in the right pan. All numbers are separated by spaces. The second line contains one of the following characters: ‘<‘, ‘>’, or ‘=’. It represents the result of the weighting:
‘<‘ means that the weight of coins in the left pan is less than the weight of coins in the right pan,
‘>’ means that the weight of coins in the left pan is greater than the weight of coins in the right pan,
‘=’ means that the weight of coins in the left pan is equal to the weight of coins in the right pan.

Output

Write to the output file the identifier of the false coin or 0, if it cannot be found by the results of the given weightings.

Sample Input

5 3
2 1 2 3 4
<
1 1 4
=
1 2 5
=

Sample Output

3

Slyar:又是假币判断问题，跟POJ1013类似，不过这个题用1013那个算法WA了…后来换了种枚举的算法才过…思路就是假币应该在每个不等式中都出现，最后只要看哪个硬币出现的次数和不等式出现的次数相同，如果这个硬币唯一，那它就是确认的假币。

```#include
#include

using namespace std;

const int MAX = 1001;

int main()
{
int n, k, p, total = 0;
char sign;
/* 记录原始数据 */
int t[MAX] = {0};
/* 标记硬币真假 */
int r[MAX] = {0};
/* 记录硬币重量 */
int w[MAX] = {0};

cin >> n >> k;

while (k--)
{
/* 读入原始数据 */
cin >> p;
for (int i = 0; i < 2 * p; i++)
{
cin >> t[i];
}

cin >> sign;
/* 标记肯定为真的硬币 */
if (sign == '=')
{
for (int i = 0; i < 2 * p; i++)
{
r[t[i]] = 1;
}
}
/* 左轻右重 */
else if (sign == '<')
{
total++;
for (int i = 0; i < p; i++)
{
w[t[i]]--;
}
for (int i = p; i < 2 * p; i++)
{
w[t[i]]++;
}
}
/* 左重右轻 */
else if (sign == '>')
{
total++;
for (int i = 0; i < p; i++)
{
w[t[i]]++;
}
for (int i = p; i < 2 * p; i++)
{
w[t[i]]--;
}
}
}

/* 假币在不等式中每次都应该出现 */
int count = 0, pos = 0;
for (int i = 1; i <= n; i++)
{
if (r[i])
{
continue;
}
/* 找出每次都出现的"假币" */
if (w[i] == total || w[i] ==  - total)
{
count++;
pos = i;
}
}

/* 假币唯一则输出 */
if (count != 1)
{
cout << 0 << endl;
}
else
{
cout << pos << endl;
}

//system("pause");
return 0;
}
```

### 网友最新评论 (1)

1. 确实，1013那题我直接枚举所有A到L的硬币情况就可以了。。。 顺便问下朋友，你那最上面的分类中的文章列表是如何弄的？求教。
Tanky Woo11年前 (2010-07-20)回复