[URAL1007]Code Words

2014-07-08
竞赛题解 / 模拟
URAL

描述 Description

A transmitter sends over a noisy line some binary code words. The receiver on the other end uses special technique to recover the original words. Every word originally consists of symbols 0 and 1. All words have the same length N (4 ≤ N ≤ 1000). After traveling through the noisy line one (but no more) of the following modifications to a word may occur:

1. Any (but only one) symbol 0 is replaced by 1.

2. Any (but only one) symbol is removed.

3. A symbol (0 or 1) is inserted at any position.

It is known that the original words all have the following property: the sum of positions where symbols 1 are located is a multiple of (N+1) or equal to zero.

输入格式 InputFormat

Input contains number N followed by received words. The words are delimited with line breaks. There will be no more than 2001 words. There is nothing else in the input data, except maybe for some extra spaces or line breaks.

输出格式 OutputFormat

Your program should print to output the original sequence of words as they were transmitted. The words should be delimited by line breaks.

样例输入 SampleInput

4
0000
011
1011
11011

样例输出 SampleOutput

0000
0110
1001
1111

来源 Source

USU Championship 1997

URAL 1007

代码 Code

! 不要在意一些细节~

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
char a[1005],ch;
inline bool ok(int x)
{
    return (x==0 || x%(n+1)==0);
}
bool oper4()
{
    int i,j,t;
    if (ok(x))
    {
        printf("%sn",a);
        return true;
    }
    return false;
}
void oper1()
{
    int i,j,t;
    for (i=0;i<m;i++) if ((a[i]=='1') && ok(x-i-1))
    {
        for (j=0;j<i;j++) printf("%c",a[j]);
        printf("0");
        for (j=i+1;j<m;j++) printf("%c",a[j]);
        printf("n");
        return ;
    }
    printf("-1n");
}
void oper2()
{
    int i,j,t;
    t=0;
    for (i=0;i<=m;i++)
    {
        if (ok(x+(y-t)))
        {
            for (j=0;j<i;j++) printf("%c",a[j]);
            printf("0");
            for (j=i;j<m;j++) printf("%c",a[j]);
            printf("n");
            return ;
        }
        if (ok(x+(y-t)+i+1))
        {
            for (j=0;j<i;j++) printf("%c",a[j]);
            printf("1");
            for (j=i;j<m;j++) printf("%c",a[j]);
            printf("n");
            return ;
        }
        if (a[i]=='1') t++;
    }
    printf("-1n");
}
void oper3()
{
    int i,j,t,k;
    t=0;
    for (i=0;i<m;i++)
    {
        k=(a[i]=='1')?1:0;
        if (ok(x-(y-t-k)-(i+1)*k))
        {
            for (j=0;j<i;j++) printf("%c",a[j]);
            for (j=i+1;j<m;j++) printf("%c",a[j]);
            printf("n");
            return ;
        }
        if (a[i]=='1') t++;
    }
    printf("-1n");
}
int main()
{
    freopen("word.in","r",stdin);
    freopen("word.out","w",stdout);
    scanf("%d",&n);
    while (scanf("%s",a)!=EOF)
    {
        m=strlen(a);    
        x=y=0;
        for (i=0;i<m;i++) if (a[i]=='1') x+=i+1,y++;
        if (n==m && oper4()) continue;
        if (n==m) oper1();
        if (m<n) oper2();
        if (m>n) oper3();
    }
    return 0;
}