707 - Robbery

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Zhou Yiyan@SHU
New poster
Posts: 12
Joined: Tue Jul 30, 2002 9:24 am
Location: SHU, Shanghai, China

707

Post 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?

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

707 - Robbery

Post 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.

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

Post by likhan »

As I have asked before, anyone who did the problem can u explain it to me?

Thanx in advance

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post 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.

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

Post 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

Rinoaheartilly
New poster
Posts: 9
Joined: Thu Oct 14, 2004 6:37 am
Location: North Carolina

707 "Robbery"

Post 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

Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

707 : Robbery

Post 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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 707 : Robbery

Post by mf »

Hi, I just solved this problem. (got a few WAs for a spelling mistake :))

[quote="

andrej2000pp
New poster
Posts: 1
Joined: Tue Aug 30, 2005 7:55 pm
Location: Prilep,Macedonia

707 Robbery

Post 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;
          }     
         }
       }
}

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post 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?

jester_vg086
New poster
Posts: 1
Joined: Mon Nov 08, 2010 4:28 am

Re: 707 - Robbery

Post 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

guissmo
New poster
Posts: 1
Joined: Fri Nov 26, 2010 5:11 pm

Re: 707 - Robbery

Post 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!

noobcake
New poster
Posts: 1
Joined: Fri Nov 26, 2010 6:18 pm

Re: 707 - Robbery

Post 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.


Post Reply

Return to “Volume 7 (700-799)”