ural-1792 Hamming Code

2016年07月12日 |

acm

| acm

• 题目：
• 代码：
• 解析&吐槽：

题目：

1792. Hamming Code
Time limit: 1.0 second
Memory limit: 64 MB
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 a petal.
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 a Hamming 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.
Problem illustration
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>
#include <queue>
#include <functional>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

int disk[4];
int pat[3];

inline bool ok()
{
    return pat[0]==(disk[1]+disk[2]+disk[3])%2 &&
            pat[1]==(disk[0]+disk[2]+disk[3])%2 &&
            pat[2]==(disk[0]+disk[1]+disk[3])%2;
}

inline void get()
{
    if(ok())
        return;
    for(int i=0;i<4;++i)
    {
        disk[i]=!disk[i];
        if(ok())
            return;
        disk[i]=!disk[i];
    }
    for(int i=0;i<3;++i)
    {
        pat[i]=!pat[i];
        if(ok())
            return;
        pat[i]=!pat[i];
    }
    throw int();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    for(int i=0;i<4;++i)
        cin>>disk[i];
    for(int i=0;i<3;++i)
        cin>>pat[i];

    get();

    for(int i=0;i<4;++i)
        cout << disk[i]<<' ';
    cout << pat[0]<<' '<<pat[1]<<' '<<pat[2]<<endl;

    return 0;
}

解析&吐槽：

每个碟片和碟片的重叠处都有一个数字，碟片的数字是 0 或 1，重叠处的数字是叠在此处的三个碟片 上数字的和除以 2 的余数。现在给出碟片和重叠处的数字，如果不符合要求，则可以改动一个数字 （碟片或重叠处的数字均可）使之符合要求，输出改正后的数字。

这道题很简单，只需要用穷举就可以做了。因为只需要改动一个数字，最多就只有七种情况，不需要 消耗多少时间。