Page 1 of 1

707

Posted: Tue Jul 30, 2002 9:35 am
by Zhou Yiyan@SHU
The problem description says, "Assuming that the robber can move at most one unit per time step". Then could the robber stay at one place for some time steps if there is no other way to go?

If I find two available routes for robber to move, should I output "Nothing known"?

B.T.W
[cpp]3 1 4
3
1 1 1 2 1
2 1 1 1 1
4 2 1 3 1
[/cpp]
what is the output?

707 - Robbery

Posted: Mon Sep 30, 2002 11:56 pm
by likhan
I did not understand the problem definition well. Is standing in one place in the next time frame a possible move. If we cannot determine a unique path in the middle but there exist a path shall we output the unique paths of the two end or "Nothing Known". And so on. Can anyone explain me the problem better.

Posted: Tue Nov 12, 2002 1:10 am
by likhan
As I have asked before, anyone who did the problem can u explain it to me?

Thanx in advance

Posted: Tue Nov 12, 2002 1:59 am
by Adrian Kuegel
Is standing in one place in the next time frame a possible move. If we cannot determine a unique path in the middle but there exist a path shall we output the unique paths of the two end or "Nothing Known".
yes, standing in one place in the next time frame is a possible move. And you should output all parts of the path you can determine, therefore you should only print "Nothing Known" if there is no timestep with a known place of the robber.

Posted: Tue Nov 12, 2002 11:31 am
by likhan
Thanx Adrien. If the first time step

######
#00#0#
######
######

2nd

######
#0000#
#0000#
######

here # stands for place which was monitored by inspector robstop and 0 where there was no monitoring.

what'll be the output.

thanx

707 "Robbery"

Posted: Mon Jan 31, 2005 8:14 pm
by Rinoaheartilly
I'm very sorry but I have a severals questions about problems. First what is L, T, R,B? I know that they are left, top, right, bottom. But left, right... to what? The problem said that the town is in rectangular shape, and the top left corner is(1,1) and the bottom right corner is (W,H). So go back to my question what are left, right , top , bottom refer to? Moreover what is "t"? Does it have anything to do with this problem? I am very sorry if I am not supposed to post questions here? Thanks

707 : Robbery

Posted: Sat Apr 02, 2005 6:37 pm
by Guest
Hello,
The problem statement does not seem very clear to me. Can anyone answer the following questions?

1. "..the robber can move at most one unit per time step", does this movement include diagonal movements as well?
2. The output will be "The robber has escaped.", only when for a specific timestep, all the blocks are blocked, or the robber cannot reach the free block(s) from possible positions of previous timestep.
3. What should the output be for a timestep when there are more than one possible location of the robber?
4. When to output "Nothing known."?

Any test case will be greatly appreciated.
Thanks.

Re: 707 : Robbery

Posted: Sat Apr 02, 2005 9:54 pm
by mf
Hi, I just solved this problem. (got a few WAs for a spelling mistake :))

[quote="

707 Robbery

Posted: Tue Aug 30, 2005 8:01 pm
by andrej2000pp
Can someone please tell me what's wrong with my code? I get WA.

Code: Select all

#include<stdio.h>
int m,n,t,mat[101][101][101],poznato[101],mozi[101],iii[101],jjj[101];
const int dx[]={0,0,0,-1,1};
const int dy[]={0,1,-1,0,0};
void memo(int i,int j,int v);
void najdipat(int i,int j,int v);
main()
{
      int tt,l,r,tp,b,i,j,k,br,test,mozii,da;
      test=0;
      while(1)
      {
       scanf("%d %d %d",&m,&n,&t);
       if(m==0 && n==0 && t==0) break;
       test++;
       
       for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
         for(k=1;k<=t;k++)
          mat[i][j][k]=-1;
       for(i=1;i<=t;i++) {mozi[i]=-1;poznato[i]=0;}
       scanf("%d",&br);
       if(br>0)
       {
       for(i=1;i<=br;i++)
       {
        scanf("%d %d %d %d %d",&tt,&l,&tp,&r,&b);
        for(j=l;j<=r;j++)
         for(k=tp;k<=b;k++)
          mat[j][k][tt]=0;
       }
       printf("Robbery #%d:\n",test);
       for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
         if(mat[i][j][1]==-1)
         {
          mat[i][j][1]=3;
          memo(i,j,1);
          }
       for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
         if(mat[i][j][t]==3)
         {
          mat[i][j][t]=1;
          najdipat(i,j,t);
          mat[i][j][t]=3;
          }
       da=1;
       for(i=1;i<=t;i++)
        if(!poznato[i]) { da=0; break;}
        
         if(!da) printf("The robber has escaped.\n");
        else{
       mozii=0;
       for(i=1;i<=t;i++)
        if(mozi[i]==1) mozii++;
       if(mozii==0) printf("Nothing known.\n");
       else for(i=1;i<=t;i++) if(mozi[i]) printf("Time step %d: The robber has been at %d,%d.\n",i,iii[i],jjj[i]);
       }
       }
       else{
            if(m==1 && m==n) for(i=1;i<=t;i++) { printf("Time step %d: The robber has been at 1,1.\n",i);}
            else printf("Nothing known.\n");
            }
       }
}
void memo(int i,int j,int v)
{
     int ii;
     if(v<t)
     {
     for(ii=0;ii<=4;ii++)
     {
     if((i+dx[ii])>=1 && (i+dx[ii])<=m && (j+dy[ii]>=1) && (j+dy[ii]<=n))
     {
      if(mat[i+dx[ii]][j+dy[ii]][v+1]==-1)
      {
       mat[i+dx[ii]][j+dy[ii]][v+1]=3;
       memo(i+dx[ii],j+dy[ii],v+1);
      }
      }
     }
     }
     else{
          mat[i][j][v]=3;
          }
}
void najdipat(int i,int j,int v)
{
int ii,jj,kk;
  if(v>1)
  {
    for(ii=0;ii<=4;ii++)
     {
     if((i+dx[ii])>=1 && (i+dx[ii])<=m && (j+dy[ii]>=1) && (j+dy[ii]<=n))
     {
      if(mat[i+dx[ii]][j+dy[ii]][v-1]==3)
      {
       mat[i+dx[ii]][j+dy[ii]][v-1]=1;
       najdipat(i+dx[ii],j+dy[ii],v-1);
       mat[i+dx[ii]][j+dy[ii]][v-1]=3;
      }
      }   
     }
    }
  else {
     for(kk=1;kk<=t;kk++)
       for(ii=1;ii<=m;ii++)
        for(jj=1;jj<=n;jj++)
         if(mat[ii][jj][kk]==1)
         {
          if(!poznato[kk]) 
           {
           mozi[kk]=1;
           poznato[kk]=1;
           iii[kk]=ii;
           jjj[kk]=jj;
           }
          else
          {

              if(ii!=iii[kk] || jj!=jjj[kk]) mozi[kk]=0;
          }     
         }
       }
}

Posted: Tue Nov 06, 2007 11:44 pm
by serur
The map corresponding to the first testcase:

At time 1:

Code: Select all

####
####
####
###o
oooo
At time 4:

Code: Select all

###o
####
####
####
oooo
Why he can't stay at X:

Code: Select all

###o
####
####
####
Xooo
all the time?

Re: 707 - Robbery

Posted: Mon Nov 08, 2010 4:30 am
by jester_vg086
what is the output for this input?

Code: Select all

5 5 5
22
1 1 1 1 2
1 1 4 1 4
1 2 1 5 5
2 1 1 1 5
2 2 1 2 2
2 2 4 2 5
2 3 1 4 5
2 5 1 5 4
3 1 1 2 5
3 3 1 3 2
3 3 4 3 5
3 4 1 4 5
3 5 2 5 5
4 1 2 1 5
4 2 1 3 5
4 4 1 4 2
4 4 4 4 5
4 5 1 5 5
5 1 1 1 4
5 2 1 4 5
5 5 1 5 2
5 5 4 5 5
0 0 0

Re: 707 - Robbery

Posted: Fri Nov 26, 2010 5:12 pm
by guissmo
jester_vg086 wrote:what is the output for this input?

Code: Select all

5 5 5
22
1 1 1 1 2
1 1 4 1 4
1 2 1 5 5
2 1 1 1 5
2 2 1 2 2
2 2 4 2 5
2 3 1 4 5
2 5 1 5 4
3 1 1 2 5
3 3 1 3 2
3 3 4 3 5
3 4 1 4 5
3 5 2 5 5
4 1 2 1 5
4 2 1 3 5
4 4 1 4 2
4 4 4 4 5
4 5 1 5 5
5 1 1 1 4
5 2 1 4 5
5 5 1 5 2
5 5 4 5 5
0 0 0
Thank you for this input! Finally got AC!

Re: 707 - Robbery

Posted: Fri Nov 26, 2010 6:25 pm
by noobcake
Here are some test cases, in case they're needed.
Input:

Code: Select all

5 5 3
2
1 1 1 4 4
2 2 2 5 5

5 5 3
2
1 1 1 4 5
2 2 1 5 5

10 1 10
1
1 2 1 10 1

10 1 5
3
1 2 1 10 1
3 1 1 2 1
3 4 1 10 1

10 1 5
3
1 2 1 10 1
4 1 1 2 1
4 4 1 10 1

100 100 100
0

1 1 3
0

1 1 1
1
1 1 1 1 1

10 1 7
8
1 2 1 10 1
3 1 1 2 1
3 4 1 10 1
6 1 1 1 1
6 3 1 3 1
6 5 1 10 1
7 1 1 2 1
7 4 1 10 1

1 2 2
1
2 1 1 1 1

5 5 5
22
1 1 1 1 2
1 1 4 1 4
1 2 1 5 5
2 1 1 1 5
2 2 1 2 2
2 2 4 2 5
2 3 1 4 5
2 5 1 5 4
3 1 1 2 5
3 3 1 3 2
3 3 4 3 5
3 4 1 4 5
3 5 2 5 5
4 1 2 1 5
4 2 1 3 5
4 4 1 4 2
4 4 4 4 5
4 5 1 5 5
5 1 1 1 4
5 2 1 4 5
5 5 1 5 2
5 5 4 5 5

0 0 0
Output:

Code: Select all

Robbery #1:
Nothing known.

Robbery #2:
The robber has escaped.

Robbery #3:
Time step 1: The robber has been at 1,1.

Robbery #4:
Time step 1: The robber has been at 1,1.
Time step 2: The robber has been at 2,1.
Time step 3: The robber has been at 3,1.

Robbery #5:
Time step 1: The robber has been at 1,1.
Time step 4: The robber has been at 3,1.

Robbery #6:
Nothing known.

Robbery #7:
Time step 1: The robber has been at 1,1.
Time step 2: The robber has been at 1,1.
Time step 3: The robber has been at 1,1.

Robbery #8:
The robber has escaped.

Robbery #9:
Time step 1: The robber has been at 1,1.
Time step 2: The robber has been at 2,1.
Time step 3: The robber has been at 3,1.
Time step 7: The robber has been at 3,1.

Robbery #10:
Time step 2: The robber has been at 1,2.

Robbery #11:
Time step 1: The robber has been at 1,3.
Time step 2: The robber has been at 2,3.
Time step 3: The robber has been at 3,3.
Time step 4: The robber has been at 4,3.
Time step 5: The robber has been at 5,3.