#include<stdio.h>
#include<string.h>
char s[100];
bool map[200][200],bo;
int n,m,x,y,xx,yy,a[11000],b[11000],c,zy;
void find(int xx,int yy,int xy)
{
    bool l,r,s,x;
    l=r=s=x=false;
    map[xx][yy]=false;
    if (map[xx+1][yy]) {printf("R");map[xx+1][yy]=false;c++;a[c]=xx+1;b[c]=yy;}
    if (map[xx][yy+1]) {printf("T");map[xx][yy+1]=false;c++;a[c]=xx;b[c]=yy+1;}
    if (map[xx-1][yy]) {printf("L");map[xx-1][yy]=false;c++;a[c]=xx-1;b[c]=yy;}
    if (map[xx][yy-1]) {printf("B");map[xx][yy-1]=false;c++;a[c]=xx;b[c]=yy-1;}
    if (xy==c) return;
    printf(",\n");
    if (xy<c)
      find(a[xy+1],b[xy+1],xy+1);

}
int main()
{
    memset(map,false,sizeof(map));
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    gets(s);
    if (strlen(s)==1)
    {
        n=s[0]-48;
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d",&x,&y);
            if (i==1)
            {
              xx=x;
              yy=y;
            }
            map[x][y]=true;
        }
        a[1]=xx;
        b[1]=xx;
        c=1;
        printf("%d %d\n",xx,yy);
        find(xx,yy,1);
        printf(".\n");
    }
    else
    {
        x=s[0]-48;
        y=s[2]-48;
        map[x][y]=true;
        zy=1;
        c=1;
        while (true)
        {
          gets(s);
          if (s[0]=='.') break;
          for (int i=0;i<=strlen(s);i++)
          {
             if (s[i]=='R')
             { c++;a[c]=x+1;b[c]=y;
               map[x+1][y]=true;
             }
             else
             if (s[i]=='T')
               {map[x][y+1]=true;c++;a[c]=x;b[c]=y+1;}
             else
             if (s[i]=='L')
               {map[x-1][y]=true;c++;a[c]=x-1;b[c]=y;}
             else
             if (s[i]=='B')
               {map[x][y-1]=true;c++;a[c]=x;b[c]=y-1;}
           }
           zy++;
           x=a[zy];
           y=b[zy];
        }
        printf("%d\n",zy);
        for (int i=1;i<=10;i++)
          for (int j=1;j<=10;j++)
            if (map[i][j]) printf("%d %d\n",i,j);
    }
}

I feel wonderful.:)

Can anybody explain me why one program can have different execution time with the same code?
My friend with my code got 0.015 but I got 0.031.

Oops =)
I send it one more time and get 0.015.
Maybe it because of server...

Edited by author 22.11.2010 21:59

I get Wa6. I don't know my error. Give me some test please.

Edited by author 07.01.2017 13:53

my first attempt based on partitions
//        1 2
//          3
//          7
//        6 4
//          8
//          5
gave WA1, is there any kind of tricks in computing smallest group? or Don`t they use sample as a test 1?

I write Pascal a few day's. I not understand and nor find my error. Please help!

My code:

function M(a,b:integer):integer ;
  begin
    if a > b then result := a
    else result := b
  end;

procedure update(t: array of integer; v, tl, tr, pos, new_val: integer) ;
  var
    tm: integer;
  begin
    if tl = tr then t[v] := new_val
    else
      begin
        tm := (tl+tr) div 2;
        if pos <= tm then
          update  (t,v*2, tl, tm, pos, new_val)
        else
          update (t,v*2+1, tm+1, tr, pos, new_val);
        t[v] := M(t[v*2], t[2*v+1]);
      end;
  end;

 var
  u, j, a, i, flag: integer;
  f : string;
  t : array of integer;

begin
readln(u);
SetLength(t,25001);
for j:=1 to 25000 do
  t[j] := -1;
i := 1;
flag := 0;
WHILE true do
  begin
    readln(a);
    if a = -1 then break;
    update(t, 2, 1, u, i, a);
    i := i + 1;
    if i = u+1 then flag := 1 ;
    if i = u+1 then i := 1 ;
    if flag = 1 then
      writeln(t[2]);
  end;
end.

Edited by author 07.03.2010 10:26

I would like some tests, in particular test #3.
Thank you.

All of the test cases invented by myself pass however I have got TLE on test #14. I would like some of these difficult tests to see. Thank you.

Could anyone provide me with an O(n) solution? My works O(n log(n))

'n' is the number of test cases and 'res' it's a function that print the number of positions that can go.

The problem is that it only reads one case, for example "a2", prints the result and ends the execution.

Why that happen?

void res(char p[2]);
int main () {
int i,n;
char pos[2];
scanf("%d", &n);
for(i=0; i<n; i++) {
    scanf("%s", &pos);
    res(pos);
}

Edited by author 05.01.2017 08:22

What's the difference in memory or similar between the next two codes when i create a new array, cause in the first case (array inside main) the message of jugde is "Run time error/Stack overflow" and in the second case (array outside main) the jugde accept the code:

Case 1:

#include <stdio.h>
#include <math.h>
int main(){
    double array[128*1024];
    int i = 0;
    unsigned long long n;
    while (scanf("%llu", &n) != EOF) {
        array[i++] = sqrt(n);
    }
//Code for print......



Case 2:

#include <stdio.h>
#include <math.h>
double array[128*1024];
int main(){
    int i = 0;
    unsigned long long n;
    while (scanf("%llu", &n) != EOF) {
        array[i++] = sqrt(n);
    }
//Code for print......

I don't understand what's wrong with my code

#include <iostream>

using namespace std;

int main()
{
    int n,i,mark;
    double t,coun;
    coun=0.0;
    cin >> n;
    for (i=0; i<n; i++)
    {
        cin >> mark;
        if (mark==3) t=0;
        coun+=mark;
    }

    if (t)  {t=coun/n;}

    if (!t) { cout << "None";}

    if (t == 5)
    {
        cout << "Named";
    }
    else if (t >= 4.5)
    {
        cout << "High";
    }
    else if (t != 0)
    {
        cout << "Common";
    }

    return 0;
}

May be u have WA2 in  this case:
1
1
output have to be:
NO

There is about nmax*nmax*smax=40 844 804 iterations and time must be about 0.1,0.2 sec. But program works >0.5 sec.
How I can to optimize my code?

const nmax=101;
      kmax=4;
      smax=4004;
      type myint=0..smax+1;
var
 ans:array[1..nmax,1..nmax] of boolean;
 count,s,t:myint;
 n,m,i,j,k,x,y,ii,jj:myint;
 command:array[1..nmax,1..nmax,1..kmax,1..2] of byte;
 memory:array[1..nmax,1..nmax,1..smax] of boolean;
 list:array[1..smax] of byte;

begin
 readln(n,m);

 for k:=1 to kmax do begin
  for i:=1 to n do begin
   for j:=1 to m do read(command[i,j,k,1],command[i,j,k,2]);
  end;
 end;

 read(s);
 for i:=1 to s do read(list[i]);

 for t:=1 to s do begin
  for i:=1 to n do begin
   for j:=1 to m do memory[i,j,t]:=false;
  end;
 end;

 count:=0;
 for i:=1 to n do begin
 for j:=1 to m do begin
  ans[i,j]:=false;
 end;
 end;

 for i:=1 to n do begin
 for j:=1 to m do begin
  t:=1;
  ii:=i;
  jj:=j;
  while(t<=s)and(not memory[ii,jj,t]) do begin
   memory[ii,jj,t]:=true;
   x:=command[ii,jj,list[t],1];
   y:=command[ii,jj,list[t],2];
   ii:=x;
   jj:=y;
   inc(t);
  end;
  if(t>s)and(not ans[ii,jj]) then begin
   inc(count);
   ans[ii,jj]:=true;
  end;
 end;
 end;

 writeln(count);
 for i:=1 to n do begin
 for j:=1 to m do begin
  if(ans[i,j]) then writeln(i,' ',j);
 end;
 end;
end.

Edited by author 04.01.2017 23:24
Now AC.
When I used a lot of memory, I got TL32. When I used a little memory, I got AC.Perhaps the cache helped.

Edited by author 23.06.2017 19:24