## 118 WA: wtf

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

Moderator: Board moderators

### 118 WA: wtf

I get WA for problem 118, which frustrates me quite a bit, since it sounds deceptively simple. I think I've read the problem carefully enough, but I might be wrong. The only 'trick' I see is the fall-over-the-edge logic, which I understand as:

next.point = getmove(current.point)
if (next.point is inside bounds) current.point = next.point;
else if (has scent) do nothing;
else { fall over; set scent(current.point); }

Is this correct?
If so, where's my implementation off?

Any help will be greatly appreciated.

Code: Select all
`# include <stdio.h># include <stdlib.h>static const char angles [] = "NESW";enum bool { false, true };enum angle { north, east, south, west };struct point { short x, y; };struct bot { struct point p; enum angle angle; enum bool lost; };struct hash { struct hash * next; struct point p; };static struct point forward (struct bot bot){   struct point p = bot.p;   switch (bot.angle)   {   case north: ++ p.y; break;   case east : ++ p.x; break;   case south: -- p.y; break;   case west : -- p.x; break;   }   return p;}# define HASHSIZE 31# define HASH(p) (((p).x * 53 + (p).y) % HASHSIZE)static struct hash * scents [HASHSIZE];# define LEFT(b) (((b).angle - 1) % 4)# define RIGHT(b) (((b).angle + 1) % 4)int main (void){   struct point max;   struct bot bot;   scanf ("%hd %hd", & max.x, & max.y);   while (      3 == scanf (         "%hd %hd %1[NESW]",         & bot.p.x, & bot.p.y, (char *) & bot.angle))   {      int i, ch;      bot.lost = false;      for (i = 0; i < 4; ++i)         if ((char) bot.angle == angles[i])            bot.angle = i;      while (getchar () != '\n');      while ((ch = getchar ()) == 'F' || ch == 'R' || ch == 'L')         if (!bot.lost) switch (ch)         {         case 'F':         {            struct point p = forward (bot);            if (p.x >= 0 && p.x <= max.x && p.y >= 0 && p.y <= max.y)               bot.p = p;            else            {               struct hash * hash = scents[HASH (p)];               for (; hash; hash = hash -> next)                  if (hash -> p.x == p.x && hash -> p.y == p.y)                     break;               if (hash == NULL) /* if unscented */               {                  /* insert new scent */                  hash = malloc (sizeof * hash);                  hash -> p = p;                  hash -> next = scents [HASH (p)];                  scents[HASH (p)] = hash;                  bot.lost = true;                  printf (                     "%hd %hd %c LOST\n",                     bot.p.x, bot.p.y, angles[bot.angle]);               }            }         }         break;         case 'R': bot.angle = RIGHT (bot); break;         case 'L': bot.angle = LEFT  (bot); break;         }      if (!bot.lost)         printf ("%hd %hd %c\n", bot.p.x, bot.p.y, angles[bot.angle]);   }   return 0;}`

-- Jonas
New poster

Posts: 7
Joined: Fri Jan 28, 2005 10:01 pm
Location: Denmark

This is the fall-over-the-edge logic:
Code: Select all
`if(next step is Not fall-over)  go to next step;else if(current position has scent)  do nothing;else  fall over and leave a scent;`

Pay attention: if current position has a scent, then the instruction to fall over toward any direction is ignored. For example: the upper-right point is (5,3), and there is a scent at (5,3). Then when a robot stand at (5,3) both going toward North and toward East will be ignored.
Hope this helps.
I stay home. Don't call me out.

ImLazy
Experienced poster

Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### thanks...

To ImLazy: thanks for you reply. Unless I'm mistaken, your suggested logic is the same as mine, except that the first condition is doubly negated ('if not not ...'). Of course, I could very well be mistaken, in which case: could you point out which part of the code is wrong?

To everyone: it's driving me crazy. I'm hoping that someone with AC could be so kind as to run the following (randomly generated) input through their solution and post the output.

Code: Select all
`20 205 11 EFFFRFLFFFLFFRFRRFLR15 7 SRRLRRLLLLLLLLLLFRRRFFFRRLRL4 17 NLFRRLRRLLFLRRFFRFRLL18 7 WLFLRRRRRFFLLRFFFR7 3 WLLFRFFRRRLRFLFRFRRL9 7 EFLLRFRFFRRLLLLRRLLLFRFRRRRFLLLLRFLFFFRF0 20 NLFFFLFFLRLLFRRFRRLRFLLF1 4 WRRFRLFLFLR5 4 SLRFLFRFFFL16 7 SLFFRFFRLRFFRFL9 4 SFLRRLLLRLFFLLFR5 19 ERRLLRRLFLLFLLRFFLRLRRLFRLFLFFLRLLFRRRF4 5 NLLFRLRRLRLFLLRFRRRRLFRLF7 12 NRLFFFLRLLRFRLRLR8 16 SRFLFFRLLRFFLLL6 7 NLLLFLLRFFFLFLLRF4 9 SRLRLFFFRRLRLLLRFLLRRRRLRRRR3 18 SRLLFRFRFRLFRFFLFFRRRLRLLRRRFFRRRRLRF9 9 NLLFLRLLLLLFRFFRLRL16 11 WLFFFLLLRRFRLFLRLFFFLRRFFLLFRRFRF3 17 NLLLRRFFFLLLFL18 3 SFLLFRLFRFR3 1 WLFRFRRFFLLRFRLLFRRRLFRLRFRRLFLLRRRF1 5 NFLLLLFRFFLRRLRLRRLF19 18 WRLLRLFFFLRFRFFLFRLFLRFRFRFLFRLFFL12 5 SLLRRFFRRLFLLRRRFRFLFRLLFLFRRFLFRLFRRRFL12 10 WRFLFRFFLFLFFFFLF3 12 NRRLRLFFRRFFLLLFFRFFLLLRRLL9 11 WFLRFFRRRLFLFFFLLLL5 18 NLLFRRFRRFRRFLFLRFFRRLLLRFLRLRRFRRLRRLL17 2 NLRFRRFFFLFFLLLRRLRFRLRLR5 7 WFRFRRLLRRL16 16 NRRRLFRLFRLLFFFRFFLFRLFLFFFFRF3 6 WRRFRRFLFRFLFRLLFFR20 11 NLRRFLFFFRFRFLRFFLLRLLLFRRFRLRR13 18 SFRRLFRLFLFFRRRLRLRFRFF3 3 SFFLFFFRLLRRRF11 17 WLLFRLFRFLLRRLLRRLLLLLFFF8 17 WLLFRFFLFFFLRFRFLLLRF18 12 SLLFLFRLFLFLRLF18 11 WRRFFLRRRFLFLLLRLFFRFLRLRFRFRFLRF14 15 ERRFLFLFRRLFFFLRRRFFFRFFFRRLFFRRFRLRL17 20 WLRRRFFFLFRRRRRFLRRR2 17 NLRRRFFFLFR20 10 WLRRRRLFRFRLLLRRRRR13 8 ERRFRLFFLRRFRLLRFFLRFRR5 14 SFFRFRFFRFLRLFLFRLLF8 10 WFFLFLRRFFRFFFRFLLRLRFFFFRFFRRFFFRRLFLL19 1 NFFFRFLFLLFRFRRRLFLRRRRFRRRFFLFRLRRLLLFF4 17 ELFFRRRLLLFRRFRLLRLFRRRRLRFLLRFFRRFLFF13 0 EFLLLFLLRRRR0 4 SLRLFRLRLFRFFLRLRFFFFLRRLLLFFFFL13 1 WLRLRFLRRFLFRLRFFRLRLLRFRLFLRFLLFRRR1 10 WRFRRRRLFRFFLRLFLFRFRFFRRLLFLFL6 9 ELRLLLFLLRRFFRFRRRFRRLRFRRRFFRRFRL13 10 ELRRRFLFLRLFRFRRRFRL6 9 ERLLRFRLLRL14 1 SFLLRRFLFRLLFFLRLFRFFRLLRFLLFFRRLFRRFF12 15 ELRLLRFRFFLLRRRRRRRRLRFLFFLFLR2 20 ERLRRRFLLFRFRFFF7 15 ERLLRLLRRLLFFRLFLLRLRLFLFFFRRRFLRF16 3 NRRRRFLRFLRFFRRRFFLFRFLRRFLFFLL2 12 SRFFFLLRRLRFRLFRFLLRR7 1 NRLLFLLLLLFLRLRLLFLFFLFRRLLFFLRLR14 19 WLFRFRLFLLRFLFLFRRFFFLRRFR1 17 WFLRLFRRFRFLFLFLRRLLRR20 15 SFLLLFLLRFRLFFFLFLLLL10 7 WLLFLFFFFFRRLRLFLRFLLLF11 19 WRRRFFLFFRFLRRLRLLFLFLL19 3 WFLFFRRLRRRFFRLRFRLRFLLFRLRRRFFRRLLRRRF8 2 WFFLLRLLFLRRFLLFFFRRFRFRFRLLLRLRL14 13 NRLRRFFLFFLLFRRFRFRRRLLLRLL2 8 SLFFFRFRFRLLLRLRRRL4 18 NLFRRFLLRFFFRLLFRLFLLLLLLLRFFRLFLFFFLLLF20 17 ELFLLFFLLRLLRFLFFFFLRFFRFLRRRLLRLR8 15 SLRLFLFRLFLRRFRLFFRLLLRRLFFRRLF10 8 WLLLLRFFFRRRLFRFRRRFFRFRFFLRRFFFLRFFR4 4 SLLRRLLFLFRLFFRRRLRLLLRLRFLR12 7 SFLRFLLFLRFFFLRLRFL5 3 NRLFLRLFRLRLLFL0 2 SLRLLFFFLRRRFLFFLRFLFLRFRRFRLLFL5 4 ERRFFRRLLFFRRLRRLLFRLFLLLLRR11 16 SFFLFRRFLFRRFFLFRLFRFLF16 13 NRFLFRLFFLLLFFRLLFLFRFFLFFFL1 8 NFRLRRRFFLLFL8 10 ELLFRFLFFRRLFRLFFLRRLFRRRLR18 20 WLRFFFRFRFFRFLFLFFLLRLRRLFFFLLRRF3 6 ELRRRLLFLFFLFRFLFRFRRLLL20 2 NRFRLLRLFRFFRRLFRLFLRLLLFRRF11 9 NFFLLLFLLLLRLRLRLFL1 0 SRRLRRFLLLFLFRF15 5 NLFLLRFFLFFFFFRFFRRLRL0 9 EFLRRRLRLFFFFLRLRFFLLRFRLLLLLFLLRLLLR11 6 ELFFFFFRLFLRLLRFF20 13 NFLFLFFFRLLLLRLLRFLFRLFFFLRRRFLFFLFRLF3 6 WFRLLRFRLFLFRRRF7 7 WRRRFLFLLFFRRRLRL4 7 WRRFFLLRRFRLRLLLLLLLLFFRRLLFFRLL17 0 SLLFRRRFRRFRFRLLFFFLRFFLRRLRF10 12 SFFRFFLFFRFLFLLFRFRRLFFLLFRRRFR`

the input is generated with the following script, just in case you care, want to generate more input or w/e:

Code: Select all
`#!/usr/bin/env python# Copyright (c) 2005 Jonas Kolker# licensed under the GNU GPL version 2 or# (at your option) any later version# ... google('GNU GPL')from sys import stdoutfrom random import randrange, choicedirs = "NSEW"cmds = "FRL"bounds = (20, 20)print bounds[0], bounds[1]for i in range (100):   print randrange(0, bounds[0]+1),   print randrange(bounds[1]+1),   print choice(dirs)   for i in xrange (randrange (10, 40)):      stdout.write (choice (cmds))   print`

... thanks for saving me from becoming a nervous wreck
New poster

Posts: 7
Joined: Fri Jan 28, 2005 10:01 pm
Location: Denmark

Maybe you already got AC...
If not, try this:
Code: Select all
`1 10 0 NLF`
teni_teni
New poster

Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Nope, no AC yet.

my new implementation (in C++) gets your suggested input right: "0 0 W LOST". If any one of you have gotten AC, could you do me the favor of running my test input through your solution? Thanks in advance.

just in case you want to see the new code, here is it:
Code: Select all
`# include <iostream># include <map># include <set># include <stdio.h># include <string># include <utility>using namespace std;struct point: public pair <int, int> { };enum direction { east, north, west, south };static struct point bounds;static map <int, int> directions;static set <struct point> scent;class bot{private:   struct point p;   int direction;   bool lost;   struct point next () const throw () {      struct point n = p;      switch (direction)      {      case east : ++n.first ; break;      case north: ++n.second; break;      case west : --n.first ; break;      case south: --n.second; break;      default: while (1) new int [16384];      }      return n;   }   static bool inside (const struct point n) throw () {      return (         n.first >= 0 and         n.first <= bounds.first and         n.second >= 0 and         n.second <= bounds.second);   }public:   bot (const struct point _p, int theta):      p (_p), direction (theta), lost (false)      {}   bool islost () const throw () { return lost; }   void left () throw () { direction = (direction + 1) & 3; }   void right () throw () { direction = (direction + 3) & 3; }   void forward (void) throw () {      const struct point n = next ();      if (inside (n)) p = n; // if not out of bounds, goto n.firstt point      else if (scent.find (p) == scent.end ()) // else if no scent      {         scent.insert (p);         lost = true;         printf ("%d %d %c LOST\n", p.first, p.second, directions[direction]);      }      // else: (if scent) do nothing.   }   ~bot () {      if (not lost)         printf ("%d %d %c\n", p.first, p.second, directions[direction]);   }};int main (void){   directions ['E'] = east ;   directions ['N'] = north;   directions ['W'] = west ;   directions ['S'] = south;   directions [east ] = 'E';   directions [north] = 'N';   directions [west ] = 'W';   directions [south] = 'S';   cin >> bounds.first >> bounds.second;   struct point start;   char theta;   while (cin >> start.first >> start.second >> theta)   {      struct bot b (start, directions[theta]);      string move;      cin >> move;      for (unsigned i = 0; i < move.size() and not b.islost(); ++i)         switch (move[i])         {         case 'L': b.left(); break;         case 'R': b.right(); break;         case 'F': b.forward(); break;         }   }   return false;}`

this page is best viewed in emacs.
New poster

Posts: 7
Joined: Fri Jan 28, 2005 10:01 pm
Location: Denmark

### output by my AC program

11 12 W
14 4 W
5 17 E
20 4 E LOST
10 2 S
7 9 N
0 20 W LOST
3 5 N
6 0 E
16 6 W
9 4 W
0 18 W
5 3 E
6 15 N
7 12 W
6 9 S
4 5 W
0 19 W LOST
10 6 S
20 10 S
0 18 W
19 4 S
3 1 N
3 6 S
13 12 S
9 4 E
11 9 E
5 14 S
7 14 N
1 19 E
19 1 E
4 8 E
20 12 E LOST
4 4 S
20 11 E LOST
12 13 S
5 1 W
16 16 E
13 15 N
17 12 E
18 10 S
17 13 N
20 20 N LOST
3 14 S
20 10 E LOST
10 12 S
4 14 S
4 17 S
20 4 E
6 20 N LOST
14 0 S LOST
2 0 S LOST
11 6 E
0 13 W LOST
4 6 E
14 8 E
7 9 N
15 3 E
14 14 E
2 20 N LOST
3 18 W
11 7 E
0 12 W LOST
4 0 S LOST
12 15 N
0 18 N
20 10 E
13 11 S
14 17 S
18 0 S LOST
4 2 E
16 10 E
4 7 W
4 20 N LOST
14 18 E
13 19 E
13 10 S
1 6 N
12 10 W
4 3 E
4 5 N
1 6 S
8 16 W
15 19 S
0 9 W LOST
5 15 W
15 20 N LOST
2 10 W
20 2 E LOST
13 11 N
3 0 S LOST
19 1 W
3 3 S
9 12 W
16 6 S
1 5 E
6 6 E
7 3 E
20 0 E LOST
7 7 N
-- This is Unix, any explanatory error message is seen as a sign of weakness
lantimilan
New poster

Posts: 11
Joined: Sat Mar 19, 2005 11:12 am
Location: HKU

### possible error source

Here are some pitfalls I encounter for p118, seemingly trivial problem

1. What you code do if enum type var was assigned soemthing off bounds, e.g.
enum direction { S,N,E,W }; and enum direction dir = 5; what is dir+1 then?

2. is your buffer large enough? instructions are length 100 at most, coordinates are 50 at most
-- This is Unix, any explanatory error message is seen as a sign of weakness
lantimilan
New poster

Posts: 11
Joined: Sat Mar 19, 2005 11:12 am
Location: HKU

I've tried the input above and compared to the lantimilan's output.
It's absolutely identical, so I'm very confused why my code is wrong.
Does someone can help?
Code: Select all
`/* removed after AC */`
Last edited by razor_blue on Mon Dec 04, 2006 3:47 am, edited 1 time in total.
razor_blue
New poster

Posts: 27
Joined: Mon Nov 27, 2006 4:44 am
Location: Indonesia

I think you havent understood the 'scent' properly. The problem states
lost robots leave a robot ``scent'' that prohibits future robots from dropping off the world at the same grid point

Check the samples...

Input:
Code: Select all
`3 30 0 SFFFFFF0 0 WFFFFFF`

Output:
Code: Select all
`0 0 S LOST0 0 W`

Because the first robot is dropped off from (0,0) and thus leaves a 'scent', the second robot sees the 'scent' in (0,0) and so it remains in the grid. Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

Thank you Jan, now I understand the problem and I got AC.
razor_blue
New poster

Posts: 27
Joined: Mon Nov 27, 2006 4:44 am
Location: Indonesia

i tried above all , but i got WA , either.
following is my code :
Code: Select all
`#include<iostream>using namespace std;int main( int argc, char * argv[] ){  int a,i,j,m,n,l[51][51],x,y,p[4]={1,1,-1,-1};  char k,d[4]={'N','E','S','W'},t[100];  cin >>m>>n;  for(i=0;i<=m;i++)    for(j=0;j<=n;j++)      l[i][j]=1;  while(cin >>x>>y>>k!=NULL){    j=0;i=0;a=1;    while(d[j]!=k)      j++;    cin.getline(t,100);cin.getline(t,100);    while(t[i]!='\0'){      if(t[i]=='F'){        if(j%2==0)          y+=p[j];        else          x+=p[j];      }      if(t[i]=='R')        j=(j+1)%4;      if(t[i]=='L')        j=(j+3)%4;      i++;      if(x>m||y>n||x<0||y<0){        if((j%2==0&&l[x][y-p[j]]==0)||(j%2==1&&l[x-p[j]][y]==0)){          if(j%2==0)            y-=p[j];          else            x-=p[j];        }        else{          a=0;          if(j%2==0)            y-=p[j];          else            x-=p[j];          l[x][y]=0;          cout <<x<<" "<<y<<" "<<d[j]<<" LOST"<<endl;          break;        }      }    }    if(a==1)      cout <<x<<" "<<y<<" "<<d[j]<<endl;  }  return 0;}`

could anyone tell me why ?? THX!!
joebin
New poster

Posts: 12
Joined: Fri Dec 29, 2006 7:18 am
Location: Taiwan

### WA...help

my code works with that big input, but im still getting WA, can someone tell me why...
Code: Select all
`Accepeted...`

I try and try this problem, for a long time, and my two errors are this:
-If the robor fall in a corner the signal have effect on 1 or 2 or 3 or 4 squares
- a newline at the end of output(!!!!!!!!!! mi long time error, frustating);
Last edited by gareve25 on Thu Aug 07, 2008 2:02 pm, edited 1 time in total.
Just beginning to make my brain more strong
gareve25
New poster

Posts: 5
Joined: Mon Feb 11, 2008 8:38 pm

### Re: 118 WA: wtf

There is a mistake in the problem description

All instruction strings will be less than 100 characters in length.

when i submitted my code with a 100 char array it gave me WA, and when i changed it to 101 with the same logic it was AC

be careful ...
C++ Is The Best.
amr saqr
New poster

Posts: 29
Joined: Tue Mar 11, 2008 6:35 pm

### Re: 118 WA: wtf

There is no fault in the program description.
For a 100 length string you can't get Accepted by a 100 SIZE array.(Think why ).
You will get the answer.
try_try_try_try_&&&_try@try.com
This may be the address of success.
Obaida
A great helper

Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 118 WA: wtf

Again ,

All instruction strings will be less than 100 characters in length.

less less less less less

that means that there will be 99 instructions at maximum not 100, so it's enough to make an array of 100 characters, 99 for the instructions and an extra char for the null character, but the 100 array didn't work, when i changed it to 101 i got AC, that's why i said there is a mistake in the problem description .
C++ Is The Best.
amr saqr
New poster

Posts: 29
Joined: Tue Mar 11, 2008 6:35 pm

Next