Page **1** of **2**

### 176 - City Navigation

Posted: **Fri Apr 12, 2002 9:31 am**

by **ntrhieu**

I have questions regard to this problem:

1) Can I turn left at an intersection ? The problem states "You may not cross a lane of traffic except at an intersection, that is you must turn right when entering or leaving a driveway." It's still not clear to me.

2) what does it mean to state that "Sections on corners have two driveways" ?

This problem is pretty nice, but I don't understand it fully to start doing it.

Can anyone help me clarify this ?

Thanks

Hieu

Posted: **Sun Apr 14, 2002 6:34 pm**

by **C8H10N4O2**

What it means is: You CAN turn left but only at intersections. You CANNOT turn left into a driveway and you CANNOT turn left out of a driveway. The houses on the intersections have two driveways, one on each street of the intersection (as shown in diagram: 01&99, 98&99, 00&01, 00&90). Hopefully, that explains it.

Posted: **Thu Oct 27, 2005 6:19 pm**

by **Abednego**

I think the "90" is a typo. It should be "98". Am I correct? I'm getting WA.

Posted: **Thu Oct 27, 2005 6:42 pm**

by **little joey**

Yes, it should be 98.

Posted: **Wed Mar 15, 2006 2:26 am**

by **Ryan Pai**

I got AC, so I'd like to share what my program assumes:

Basically, ignore houses and consider every driveway as distinct (even if they do go to the same house).

I don't know if the same driveway can be both the source and destination, but I answer 0 in that case.

I define "cul de sac" when a car cannot go through with its normal route, so it might even happen at an "intersection" if the three other ways are blocked off. As a side note, the plural of "cul de sac" is "culs de sac."

And an obvious hint (but what I missed for a while), be careful about not going off the map.

Posted: **Tue Oct 17, 2006 5:22 am**

by **yiuyuho**

Hi,

Basically, ignore houses and consider every driveway as distinct (even if they do go to the same house).

Well, I coded it so that you can start from either driveway if you're on a corner, and take the minimum, I got AC too! I guess cases like that was never tested (The given driveway is always the faster one for houses on corners).

### 176 City Navigation. WA but it needs rejudge.

Posted: **Thu Feb 08, 2007 6:40 am**

by **rickyliu**

I found a program which produces incorrect result but got AC. Here is my testing data:

Code: Select all

```
A11 1098 1098
S11 1098 1098
S11 1100 1100
S06 1988 2026
S06 2180 2238
S06 2362 2396
#
S16 1288 S16 1288
S06 2301 S06 2101
A11 1102 A11 1103
#
```

The AC program produces the result as follows:

The correct one should be:

Would anyone please confirm this?

Also, I don't understand the following statements in the question:

# Streets and Avenues are numbered from 00 to 49 and there are no roads beyond these bounds; however there are driveways on both sides of the bounding roads.

# Sections on corners have two driveways.

At the top left corner, which of the following diagram is correct? The AC program does not like any of these. Maybe there is a correct answer D?

(A)

Code: Select all

```
A49
--------------
| ____ ____
| | | | |
| | | | |
| ---- ----
| ____ ____
| | | | |
```

(B)

Code: Select all

```
A49 A48
--------------
| ____ ____
| | | | |
| | | | |
| ---- ----
| ____ ____
| | | | |
```

(C)

Code: Select all

```
A49
--------------
|______ ____
| | | | |
| | | | |
|------ ----
|______ ____
| | | | |
```

I hope you understand my drawings.

Posted: **Fri Mar 02, 2007 6:19 am**

by **rickyliu**

Does anyone help to confirm the input/output?

For the clarification part, I used the following input to test the AC program:

### Re: 176 City Navigation. WA but it needs rejudge.

Posted: **Sun Mar 18, 2007 2:58 pm**

by **Carlos**

rickyliu wrote:
Code: Select all

```
A49
--------------
| ____ ____
| | | | |
| | | | |
| ---- ----
| ____ ____
| | | | |
```

That should be correct. I can't add any test case since it's not a multiple input program.

Posted: **Mon Apr 16, 2007 10:01 am**

by **Hackson**

I don't know if I am asking in the right place, but I am really confused by the problem statement (I don't understand the sample too!). Would anyone mind spending some time explaining the problem statement? Many thanks and sorry for my poor English

### Re: 176 - City Navigation

Posted: **Thu Jun 12, 2008 10:23 pm**

by **Jan**

I am trying to understand this problem (for a long time!!!). But couldn't figure out 'what is the actual map' and 'what does the problem really want'.

What if I use the following route for the sample input?

So, how can be the number of driveways passed is 213? Can anyone explain please?

Thanks in advance.

### Re: 176 - City Navigation

Posted: **Fri Jun 13, 2008 8:24 pm**

by **yiuyuho**

You may not cross a lane of traffic except at an intersection, that is you must turn right when entering or leaving a driveway.

That is you may not turn left when you leave the source location. Also you are driving on the right hand side of the road, so you wont have the U-turn at the end, instead you would turn right onto the "right lane" of Street 16 and enter the destination (also by turning right).

### Re: 176 - City Navigation

Posted: **Fri Jun 13, 2008 9:28 pm**

by **Jan**

Still I can't understand. Sorry.

For the sample I was going to the east at 16th street. I found a dead end, so, I changed the lane. Then at the intersection (16th street, 13th avenue) I took right. Then at 15th street I took right again. This way I am reaching the destination. May be am sounding stupid. But I can't really understand.

Can you explain the sample, please? Or just show the first few moves. Thanks again.

### Re: 176 - City Navigation

Posted: **Fri Jun 13, 2008 9:49 pm**

by **yiuyuho**

Well, I am sorry. It seems I made a mistake and swapped the source and destination. The route on your map seems correct. Here's the calculation on the driveways to get 213:

Starting from S16 1288:

1288 --> 1252: excluding 1288 this gives 18 driveways

1253 --> 1299: inclusive, this gives 24 driveways

Then you travel 3 complete blocks each having 50 driveways: 150

Finally, 1501 --> 1543: excluding 1543 this gives 21 driveways.

In total, 18+24+150+21 = 213

Is this correct now?

Posted: **Thu Nov 20, 2008 11:44 pm**

by **amantzaris**

Are the input addresses given in order (source/destination), or do we need to compute the minimum between both directions?