var
  n: integer;
  s: string;

  function Go(s: string): string;
   var
    sum: integer;
    i: integer;
    j: integer;
    stmp: string;
    tmp: integer;
   begin
    s:=trim(s);

    sum:=0;
    for i:=1 to length(s) do
     if s[i]='1' then sum:=sum+i;

    if (length(s)=n) and (sum mod (n+1) = 0) then
                              begin
                               result:=s;
                               exit;
                              end;

   if (length(s)=n-1) then
                       begin
                        if sum mod (n+1) = 0 then
                            result:=s+'0' else
                            result:=s+'1';
                        exit;
                       end;

   if (length(s)=n+1) then
                        begin
                         for i:=1 to length(s) do
                          begin
                          stmp:=s;
                          Delete(stmp,i,1);
                          tmp:=0;

                          for j:=1 to length(stmp) do
                           if stmp[j]='1' then tmp:=tmp+j;

                           if tmp mod (n+1) = 0 then
                             begin
                              result:=stmp;
                              exit;
                             end;
                          end;
                        end;
   for i:=length(s) downto 1 do
    if (s[i]='1') then
        if
        ((sum-i) mod (n+1) = 0)
        then begin s[i]:='0'; break; end else
    else if ((sum+i) mod (n+1) = 0)
        then begin s[i]:='1'; break; end;
    result:=s;
   end;

begin
//  assign(input,'input.txt'); reset(input);

  readln(n);

  while not eof do
   begin
    readln(s);

    writeln(Go(s));
   end;

 // sleep(12121);
end.

Welcome to the next http://codeforces.com/ round.

I'm glad to invite you to take part in Codeforces Beta Round #3. It
starts on Thursday, March 4, 2010 19:30 (UTC +3, Moscow time). Click
http://www.timeanddate.com/worldclock/fixedtime.html?year=2010&month=03&day=04&hour=16&min=30&sec=0&p1=0
to view the time in the other time zones. The contest duration is 2
hours.
The allowed programming languages are C/C++, Pascal, Java, C#, Python,
Ruby and PHP.

Recently we have introduced Codeforces rating system. Currently
vepifanov is the highest-rated coder, but Codeforces is at the initial
stage now, and all sorts of changes can be introduced in future. Want
to compete? - click http://codeforces.com/contests/

If you are Russian speaking try http://codeforces.ru/.

Wish you high rating,
MikeMirzayanov
---
http://codeforces.com/
http://codeforces.ru/

http://acm.timus.ru/rating.aspx?space=1&num=1001&count=10
solution of the problem requires an array of 128 * 1024 elements
and an element of the array must store 13 digits, ie double, whose size is 8 bytes.
128 * 1024 * 8 = 1MB of memory
how to solve the problem using 730Kb or less?

var
b,a:array[1..50000]of int64;
n,m,i,j:longint;
begin

readln(n);
for i:=1 to n do
readln(a[i]);

readln(m);
for j:=1 to m do
readln(b[j]);

for i:=1 to n do
for j:=1 to m do
if a[i]+b[j]=10000 then begin writeln('YES'); halt(0);end;
writeln('NO');
end.

I got WA#1. But my program gives correct result for all tests what i found on this forum.
Why WA#1?
Please give tests where my program will give incorrect result.
My source code:
////////////////////////////
///Stupid brute force
#include <iostream>
#include <cstdio>
using namespace std;

int mem[30000];
//set<int> fb;

int main()
{
    char a[100];
    char c;
    int ltd=0;
    int i;
    for(i=0;i<30000;i++)mem[i]=0;
    while(!cin.eof())
    {
        cin.getline(a,100);
        int t,mp;
        sscanf(a,"%d %c%d",&t,&c,&mp);
        mp--;
        int mfb=40000;
        for(i=0;i<30000;i++)
        {
            mem[i]-=t-ltd;
            if((mem[i]<1)&&(i<mfb)){mfb=i;if(t==ltd)break;}
        }
        if(c=='+')
        {
            mem[mfb]=600;
            cout<<mfb+1<<'\n';
        }
        else
        {
            if(mem[mp]>0){mem[mp]=600;cout<<"+\n";}
            else cout<<"-\n";
        }
        ltd=t;
    }
    return 0;
}

my code is
#include<stdio.h>
#include<string.h>
int main()
{
    char a[10];
    while(scanf("%s",a)==1)
    {
        long int s1=0,s2=0;
        long int len = strlen(a);
        for(long int i=0;i<len;i++)
        {
            if(i<3)
                s1 = s1 + (a[i]-'0');
            else
                s2 = s2 + (a[i] - '0');
        }
        long int sub = s1 - s2;

        if(sub ==1 || sub== -1)
        {
            if(sub==1)
            {
                long int add = (a[len-1]-'0')+1;
                if(add>9)
                {
                    printf("No\n");
                }
                else
                printf("Yes\n");
            }
            else if(sub == -1)
            {
                if(a[len-1]<1)
                printf("No\n");
                else
                printf("Yes\n");
            }
        }
        else
            printf("No\n");
    }
    return 0;
}

i don't know where is my problem. please help me.

Why I have wa #2?
My solution:
///////////////
#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;

#define mkpair make_pair

int main()
{
    int n,m;
    char a[300];
    cin.getline(a,300);
    int fmt=sscanf(a,"%d%d",&n,&m);
    bool fmt1;
    bool pic[10][10];
    bool pic2[10][10];
    int ml[10],md[10];
    if(fmt==1)fmt1=true;else fmt1=false;
    if(fmt1)
    {
        int i,j,x,y;
        for(i=0;i<10;i++)
            for(j=0;j<10;j++){pic[i][j]=false;pic2[i][j]=false;}
        for(i=0;i<10;i++){ml[i]=100;md[i]=100;}
        for(i=0;i<n;i++)
        {
            cin>>x>>y;
            x--;y--;
            pic[y][x]=true;
            if(ml[y]>x)ml[y]=x;
            if(md[x]>y)md[x]=y;
        }
        int mdl=100,mdd=-1;
        for(i=0;i<10;i++)
        {
            if(ml[i]<mdl)mdl=ml[i];
        }
        mdd=md[mdl];
        cout<<mdl+1<<" "<<mdd+1<<"\n";
        queue<pair<int,int> > pc;
        pc.push(mkpair(mdl,mdd));
        while(!pc.empty())
        {
            x=pc.front().first;y=pc.front().second;pc.pop();
            pic2[y][x]=true;
            if(x<9 && !pic2[y][x+1] && pic[y][x+1]){cout<<"R";pic2[y][x+1]=true;pc.push(mkpair(x+1,y));}
            if(y<9 && !pic2[y+1][x] && pic[y+1][x]){cout<<"T";pic2[y+1][x]=true;pc.push(mkpair(x,y+1));}
            if(x>0 && !pic2[y][x-1] && pic[y][x-1]){cout<<"L";pic2[y][x-1]=true;pc.push(mkpair(x-1,y));}
            if(y>0 && !pic2[y-1][x] && pic[y-1][x]){cout<<"B";pic2[y-1][x]=true;pc.push(mkpair(x,y-1));}
            if(pc.empty())cout<<".\n";else cout<<",\n";
        }
    }
    else
    {
        queue<pair<int,int> > pc;
        pc.push(mkpair(n-1,m-1));
        int i,j;
        for(i=0;i<10;i++)
            for(j=0;j<10;j++){pic[i][j]=false;pic2[i][j]=false;}
        int cnt=0;
        bool dr=true;
        while(!pc.empty())
        {
            cnt++;
            int y=pc.front().second,x=pc.front().first;pc.pop();
            pic[y][x]=true;
            char c='\0';
            while((c!=',')&&(c!='.')&&(dr))
            {
                cin>>c;
                switch(c)
                {
                    case 'R':pic[y][x+1]=true;
                        pc.push(mkpair(y,x+1));
                        break;
                    case 'T':pic[y+1][x]=true;
                        pc.push(mkpair(y+1,x));
                        break;
                    case 'L':pic[y][x-1]=true;
                        pc.push(mkpair(y,x-1));
                        break;
                    case 'B':pic[y-1][x]=true;
                        pc.push(mkpair(y-1,x));
                        break;
                }
                dr=(c!='.');
            }
        }
        int y,x;
        cout<<cnt<<'\n';
        for(x=0;x<10;x++)
            for(y=0;y<10;y++)
                if(pic[y][x])cout<<x+1<<' '<<y+1<<'\n';
    }
    return 0;
}
//////////////////////////

C99 7.20.6.1: long long int llabs(long long int j);
but when I submit my code with use of llabs, I got CE.

I use shortest path to solve this problem...

I used SPFA, but failed in test 8. Who can help me?

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
int op[] = {0, 2, 1, 5, 6, 3, 4};
int r[7][7] = {
    {0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 4, 5, 6, 3},
    {0, 0, 0, 6, 3, 4, 5},
    {0, 6, 4, 0, 1, 0, 2},
    {0, 3, 5, 2, 0, 1, 0},
    {0, 4, 6, 0, 2, 0, 1},
    {0, 5, 3, 1, 0, 2, 0}
};
struct State {
    int x, y, b, f; //表示坐标(x, y)和底面和前面上的标号
} beg, end, que[24*8*8*100];
bool inque[9][9][7][7];
int dist[9][9][7][7], a[7], path[24*8*8*2];
int ans = 1000000000, last;
char s1[4], s2[4];

void eval(State &s, int x, int y, int b, int f)
{
    s.x = x, s.y = y, s.b = b, s.f = f;
}
bool check(State &s)
{
    if (s.x == 0 || s.x > 8 || s.y == 0 || s.y > 8) return 0;
    return 1;
}
void SPFA()
{
    int closed = 0, open = 2;
    memset(dist, 0x3f, sizeof(dist));
    eval(que[1], beg.x, beg.y, beg.b, beg.f);
    inque[beg.x][beg.y][beg.b][beg.f] = 1;
    dist[beg.x][beg.y][beg.b][beg.f] = 0;
    do {
        closed++;
        inque[que[closed].x][que[closed].y][que[closed].b][que[closed].f] = 0;
        if (que[closed].x == end.x && que[closed].y == end.y && dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] < ans) {
            ans = dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f];
            last = closed;
        }
        State newst;
        // forward
        eval(newst, que[closed].x, que[closed].y-1, que[closed].f, op[que[closed].b]);
        if (check(newst)) {
            if (dist[newst.x][newst.y][newst.b][newst.f] > dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b]) {
                dist[newst.x][newst.y][newst.b][newst.f] = dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b];
                if (!inque[newst.x][newst.y][newst.b][newst.f]) {
                    inque[newst.x][newst.y][newst.b][newst.f] = 1;
                    que[open] = newst;
                    path[open] = closed;
                    open++;
                }
            }
        }
        // right
        eval(newst, que[closed].x+1, que[closed].y, r[que[closed].b][que[closed].f], que[closed].f);
        if (check(newst)) {
            if (dist[newst.x][newst.y][newst.b][newst.f] > dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b]) {
                dist[newst.x][newst.y][newst.b][newst.f] = dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b];
                if (!inque[newst.x][newst.y][newst.b][newst.f]) {
                    inque[newst.x][newst.y][newst.b][newst.f] = 1;
                    que[open] = newst;
                    path[open] = closed;
                    open++;
                }
            }
        }
        // backward
        eval(newst, que[closed].x, que[closed].y+1, op[que[closed].f], que[closed].b);
        if (check(newst)) {
            if (dist[newst.x][newst.y][newst.b][newst.f] > dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b]) {
                dist[newst.x][newst.y][newst.b][newst.f] = dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b];
                if (!inque[newst.x][newst.y][newst.b][newst.f]) {
                    inque[newst.x][newst.y][newst.b][newst.f] = 1;
                    que[open] = newst;
                    path[open] = closed;
                    open++;
                }
            }
        }
        // left
        eval(newst, que[closed].x-1, que[closed].y, op[r[que[closed].b][que[closed].f]], que[closed].f);
        if (check(newst)) {
            if (dist[newst.x][newst.y][newst.b][newst.f] > dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b]) {
                dist[newst.x][newst.y][newst.b][newst.f] = dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b];
                if (!inque[newst.x][newst.y][newst.b][newst.f]) {
                    inque[newst.x][newst.y][newst.b][newst.f] = 1;
                    que[open] = newst;
                    path[open] = closed;
                    open++;
                }
            }
        }
    } while (closed < open);
}
void print(int i)
{
    if (que[i].x == beg.x && que[i].y == beg.y) {
        printf("%d %c%d", ans+a[beg.b], beg.x+'a'-1, beg.y);
        return;
    }
    print(path[i]);
    printf(" %c%d", que[i].x+'a'-1, que[i].y);
}
int main()
{
    scanf("%s%s%d%d%d%d%d%d", s1, s2, &a[1], &a[2], &a[3], &a[4], &a[5], &a[6]);
    beg.x = s1[0] - 'a' + 1;
    beg.y = s1[1] - '0';
    beg.b = 5;
    beg.f = 1;
    end.x = s2[0] - 'a' + 1;
    end.y = s2[1] - '0';
    SPFA();
    print(last);
    printf("\n");
    return 0;
}

I got the following answer when tried to send test to Timus team:
   ----- The following addresses had permanent fatal errors -----
judge_mailbox@busin.usu.ru
    (reason: 550 5.1.1 User unknown)
    (expanded from: <timus_support@acm.timus.ru>)

   ----- Transcript of session follows -----
550 5.1.1 judge_mailbox@busin.usu.ru... User unknown

Maybe someone could give me some tests to find the bug in my program. I have tried the tests on this forum(and others) and it provides the correct answer(for those tests).
L.E.: Never mind, I got accepted. Using an automated test generator, which I wrote, I found that my program failed to provide a correct answer on the following test:
//Input
2
-1 -1
//Correct Output
1
//My Output
-1
And obviously, it failed all tests of the type
n
-1 -1 ... -1
by providing the answer -1. Maybe this will help others of wasting a few days on the problem.

Edited by author 23.02.2010 21:27

what's wrong???

var a:array[1..1000] of string;v,b,c,n,i:integer;
begin
b:=0;c:=0;v:=0;
read(n);
for i:=1 to n+1 do begin
readln(a[i]);
if a[i]='Emperor Penguin' then v:=v+1;
if a[i]='Macaroni Penguin' then b:=b+1;
if a[i]='Little Penguin' then c:=c+1;
end;
if (v>b)and(v>c)then writeln('Emperor Penguin');
if (b>v)and(b>c)then writeln('Macaroni Penguin');
if (c>b)and(c>v)then writeln('Little Penguin');
end.

Why I got crash on 10 test????

var a:array[1..100]of string;
n,i:integer; c:string;
begin
read(n);
for i:=1 to n+1 do readln(a[i]);
readln(c);
for i:=1 to n+1 do if pos(c,a[i])=1 then writeln(a[i]);
end.

//============================================================================
// Name        : 1001. Reverse root
// Author      : Efrén Fuentes
// Version     : 1.00
// Copyright   : Efrén Fuentes. 2010
// Description : Imprimir las raices cuadradas en orden inverso
//============================================================================

#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

class Nodo {
public:
    long double valor;
    Nodo *anterior;
};

class Pila {
public:
    Nodo *tope;

    Pila() {
        tope = NULL;
    }

    void Push(long double valor) {
        Nodo *nuevo = new Nodo();
        nuevo->valor = valor;
        nuevo->anterior = tope;
        tope = nuevo;
    }

    void PushRaiz(long double valor) {
        Push(sqrt(valor));
    }

    long double Tope() {
        Nodo *ultimo = tope;
        long double valor = tope->valor;

        tope = ultimo->anterior;

        return valor;
    }
};

int main() {
    // declarar variables
    long double numero;
    Pila *pila = new Pila();

    // leer valores
    while(!cin.eof()) {
        cin >> numero;
        pila->PushRaiz(numero);
    }

    // el ultimo numero ingresa dos veces en la pila
    // hay que eliminarlo
    pila->Tope();

    // formatear la salida con 4 decimales
    cout << setiosflags(ios::fixed) << setprecision(4);

     // mostrar las raices
    while(pila->tope != NULL) {
        cout << pila->Tope() << endl;
    }

    return EXIT_SUCCESS;
}

C99 7.12.7.3 (page 228) specifies the hypot functions. But I suspect that there is something wrong with them here. When I call hypot() to calculate the distance I got WA. But if adding this fragment of code:
double dist(double x, double y) { return sqrt(x * x + y * y); }
and call dist() instead of hypot() I got AC. Seems the C Compiler is not compatible with C99. I hope the administrators can update their C compiler.

Upgrade of Timus test server happened on autumn 2008. I became several times faster, but very few time limits were changed. This problem is one that needs time limit to be lowered. Because with 1s TL and new servers some brute force solutions get AC - solutions that would never get AC on old testing server.

I suggest TL=0.2s considering that some languages (Java and C#) need about 0.1s to start program.

I solved this problem by probabilistic approach and brute-force. No TLE, just stupid WA :)