Timus 1792. Hamming Code 题解

Let us consider four disks intersecting as in the figure. Each of the three shapes formed by the intersection of three disks will be called apetal.

Write zero or one on each of the disks. Then write on each petal the remainder in the division by two of the sum of integers on the disks that contain this petal. For example, if there were the integers 0, 1, 0, and 1 written on the disks, then the integers written on the petals will be 0, 1, and 0 (the disks and petals are given in the order shown in the figure).

This scheme is called aHamming code. It has an interesting property: if you enemy changes secretely any of the seven integers, you can determine uniquely which integer has been changed. Solve this problem and you will know how this can be done.

Input

The only line contains seven integers separated with a space, each of them being zero or one. The first four integers are those written on the disks in the order shown in the figure. The following three integers are those written on the petals in the order shown in the figure

Output

Output one line containing seven integers separated with a space. The integers must form a Hamming code. The set of integers may differ from the input set by one integer at most. It is guaranteed that either the input set is a Hamming code or a Hamming code can be obtained from it by changing exactly one integer.

Samples

input output

0 1 0 1 1 0 1	0 1 0 0 1 0 1
1 1 1 1 1 1 1	1 1 1 1 1 1 1

这样的题目就是考理解题目的能力了。

因为数据十分小，所以使用上面方法都不会超时的，只要答案对就可以了。

所以遇上这样的题目就暴力吧。

#include <iostream>
using namespace std;

void countHammingCode(int B[])
{
	B[4] = (B[1] + B[2] + B[3])%2;
	B[5] = (B[0] + B[2] + B[3])%2;
	B[6] = (B[0] + B[1] + B[3])%2;
}

void HammingCode()
{
	int A[7], B[7];
	for (int i = 0; i < 7; i++)
	{
		cin>>A[i];
		B[i] = A[i];
	}
	bool ok = false;
	for (int k = -1; k < 4; k++)
	{
		if (-1 != k) B[k] = !B[k];
		countHammingCode(B);
		ok = true;
		for (int i = 4; i < 7; i++)
		{
			if (A[i] != B[i]) ok = false;
		}
		if (ok) 
		{
			for (int i = 0; i < 7; i++)
			{
				cout<<B[i]<<' ';
			}
			break;
		}
		if (-1 != k) B[k] = !B[k];
	}
	if (!ok)
	{
		countHammingCode(B);
		for (int i = 4; i < 7; i++)
		{
			A[i] = !A[i];
			ok = true;
			for (int j = 4; j < 7; j++)
			{
				if (A[j] != B[j]) ok = false;
			}
			if (ok) 
			{
				for (int j = 0; j < 7; j++)
				{
					cout<<B[j]<<' ';
				}
				break;
			}
			A[i] = !A[i];
		}
	}
}

int main()
{
	HammingCode();
	return 0;
}

觉得上面代码不够简洁的，可以参考下面代码：

void mainHammingCode()
{
	int i,m[8];
	for(i=1; i<8; i++) scanf("%d", &m[i]);

	for(i=1; i<9; i++)
	{
		if( (m[2]+m[3]+m[4])%2 == m[5] &&
			(m[1]+m[3]+m[4])%2 == m[6] &&
			(m[1]+m[2]+m[4])%2 == m[7]) break;
		m[i]=(!m[i]);
		m[i-1]=(!m[i-1]); 
	}
	for(i=1;i<8;i++) printf("%d ",m[i]);
}