OK

Thank you. New tests were added, and many authors lost AC.

The Answer is ?

You can do it like this:
printf("%.0lf\n", res);

Oh,my god!
Don't the author say all values are longint?

... whereas

F(i,n) { string str; cin >> str; s.push_back(str); }

results in 0.109 seconds and 500 KB of wasted memory.

No. This test no correct. He does not qualify under the condition of the problem.

Edited by author 05.03.2010 02:28

!!!!!EXTENDED for Pascal!!!!!!
!!!!!LONG DOUBLE for C++!!!!!!

use dinamic memory try
double *a = (double *) malloc (sizeof(double)*128*1024);
and when you done before return
free (a);
thats all :)

Well, after I started to use double instead of float, it passed the test.

When I was using strings,I had MLE 8. Bit in my AC programm I used arrays of char.

up

This problem is not so memory consuming. Java solution using variable
char field[][] = new char[1 + n + 1][1 + n + 1];
gets AC.

So it is possible to store whole input in memory, but it is impossible to store significant amount of data for each cell. For example 4 arrays NxN of 16-bit ints need extra 16 Mb of memory while total ML is 16 Mb.

N*(N+1)/2

see also this (or give more test data):

#include <iostream>
#include <string>

using namespace std;

short N;
char word[2001][1001];

int main(){
    int i=0,j,n,s=0,c=0,temp;
    cin>>N;
    while(cin>>word[i])i++;
    n=i;
    for(i=0;i<n;i++){
////////////////////// CASE 1 (REPLACED)//////////////////////
        if(strlen(word[i])==N){
            for(j=0;j<N;j++)
                if(word[i][j]=='1')s+=j+1;
            s%=(N+1);
            word[i][s-1]='0';
        }
////////////////////// CASE 2 (REMOVED)//////////////////////
        else if(strlen(word[i])==N-1){
            for(j=0;j<N-1;j++)
                if(word[i][j]=='1'){
                    s+=j+1;
                    c++;
                }
            s%=(N+1);
            if(s!=0)s=N+1-s;
            if(s<=c){    // Removed '0'
                for(j=N-2;s!=0;j--){
                    word[i][j+1]=word[i][j];
                    if(word[i][j]=='1')s--;
                }
                word[i][j+1]='0';
            }
            else {    // Removed '1'
                short mod=s;
                c=0;
                for(j=s;j<N-1;j++)
                    if(word[i][j]=='1')c++;
                while(s+c!=mod){
                    s--;
                    if(word[i][s-1]=='1')c++;
                }
                for(j=N-1;j>=s;j--)word[i][j]=word[i][j-1];
                word[i][s-1]='1';
            }
        }
////////////////////// CASE 3 (INSERTED)//////////////////////
        else if(strlen(word[i])==N+1){
            for(j=0;j<N+1;j++)
                if(word[i][j]=='1')s+=(j+1);
            s%=(N+1);
            for(j=N;j>=0 && c!=s;j--)
                if(word[i][j]=='1')c++;
            if(j>=0 && word[i][j]=='0'){ // Inserted '0'
                for(;j<N;j++)word[i][j]=word[i][j+1];
                word[i][j]=0;
            }
            else {    // Inserted '1'
                if(s==0)s=N+1;
                short mod=s;
                c=0;
                for(j=s;j<N+1;j++)
                    if(word[i][j]=='1')c++;
                while(s+c!=mod){
                    s--;
                    if(word[i][s]=='1')c++;
                }
                for(j=s-1;j<N+1;j++)word[i][j]=word[i][j+1];
                word[i][j]=0;
            }
        }
        s=c=0;
    }
    for(i=0;i<n;i++)cout<<word[i]<<endl;
    return 0;
}

execution time depends on at what time starts the test?
ie of server load?

Try to use the array of chars:)