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:

Code: Select all

-1
333
(Program crashed)
The correct one should be:

Code: Select all

0
261
2
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. :wink:

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:

Code: Select all

Code removed ..

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 :oops:

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