2014
02-24

# Communication Channels

Classical information theory is based on the concept of a communication channel.

Information theory is generally considered to have been founded in 1948 by Claude Shan-non in his seminal work, \A Mathemati-cal Theory of Communication." The cen-tral paradigm of classical information theory is the engineering problem of the transmis-sion of information over a noisy channel. http://en.wikipedia.org/wiki/Information theory

In this problem, we will specifically consider one of the simplest possible noisy channels, namely the binary symmetric channel (BSC). A BSC transmits a sequence of bits, but each transmitted bit has a probability p of being fiipped to the wrong bit. This is called the crossover probability, as can be understood from the figure. We assume independent behaviour on difierent bits, so a communication of l bits has probability (1 – p)^l of being transmitted
correctly. Note that one can always assume that p < 1/2, since a channel with p = 1/2 is totally useless, and a channel with p > 1/2 can easily be transformed to a new channel having crossover probability 1 – p by just flipping all bits of the output.

Of course, it is still possible to communicate over a noisy channel. (In fact, you are doing it all the time!) To be able to do this, one has to add extra bits in order for the receiver to detect or even possibly correct errors. Example implementations of such a feature are parity bits, Cyclic Redundancy Checks (CRC) and Golay codes.

These are not relevant to this problem, however, so they will not be discussed here.

In this problem you must investigate the behaviour of a binary symmetric channel.

The first line of the input consists of a single number T, the number of transmissions.

Then follow T lines with the input and the output of each transmission as binary strings, separated by a single space.

The first line of the input consists of a single number T, the number of transmissions.

Then follow T lines with the input and the output of each transmission as binary strings, separated by a single space.

2
10 10
10 11

OK
ERROR

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#define PB push_back
#define MP make_pair
#define clr(a,b) (memset(a,b,sizeof(a)))
#define rep(i,a) for(int i=0; i<(int)a.size(); i++)

const int INF = 0x3f3f3f3f;
const double eps = 1E-8;

char s1[1000],s2[1000];
int T;

int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s%s",s1,s2);
if(strcmp(s1,s2) == 0)	puts("OK");
else	puts("ERROR");
}

return 0;
}