Why I've got MLE(19 MB). I use KMP and I don't understand why at all! I appeal to you for help...
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main() {
  int  i, j, f=0, n;
  string what_to_find, gde;
  cin>>n>>what_to_find>>gde;
  what_to_find+="#";
  what_to_find+=gde;
  what_to_find+=gde;
  gde="";
  vector<short> next(what_to_find.size());
  next[0]=0;
  for(i=1; i<what_to_find.size(); i++){
    if(what_to_find[i]==what_to_find[next[i-1]])
      next[i]=next[i-1]+1;
    else {
      j = next[i-1];
      while (j>0 && what_to_find[i]!=what_to_find[j]){
      j=next[j-1];
      if(what_to_find[i]==what_to_find[j])
        next[i]=j+1;
      }
    }
    if(next[i]==n) {
      f=1;
      break;
    }
  }

  if(f) cout<<i-2*n;
  else cout<<-1;
  return 0;

}

подсмотренная ими у каких подвыпивших космонавтов
->
подсмотренная ими у каких-то подвыпивших космонавтов

If you use Java pay attention to size of arrays, that you used.
I used 2 arrays for saving current line and prev line of input(every has o(n) elements), and 2 arrays for saving result of calculating in prev Line, and for saving result of calculation in current line (every has o(n) elements).

Edited by author 21.02.2010 15:56

Make a table of first 3401 primes to factor n; use BigInteger.modInverse instead of coding extended GCD algorithm.

Who knows what does Output limit exceeded mean?

  thanks.

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.