176 - City Navigation

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

Moderator: Board moderators

ntrhieu
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am

176 - City Navigation

Post by ntrhieu » Fri Apr 12, 2002 9:31 am

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

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Sun Apr 14, 2002 6:34 pm

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.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Oct 27, 2005 6:19 pm

I think the "90" is a typo. It should be "98". Am I correct? I'm getting WA.
If only I had as much free time as I did in college...

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Oct 27, 2005 6:42 pm

Yes, it should be 98.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Wed Mar 15, 2006 2:26 am

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.
I'm always willing to help, if you do the same.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Tue Oct 17, 2006 5:22 am

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

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

176 City Navigation. WA but it needs rejudge.

Post by rickyliu » Thu Feb 08, 2007 6:40 am

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:

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu » Fri Mar 02, 2007 6:19 am

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

User avatar
Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

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

Post by Carlos » Sun Mar 18, 2007 2:58 pm

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.
DON'T PM ME --> For any doubt, suggestion or error reporting, please use the "Contact us" form in the web.

Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

Post by Hackson » Mon Apr 16, 2007 10:01 am

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:
Solving problem is a no easy task...

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 176 - City Navigation

Post by Jan » Thu Jun 12, 2008 10:23 pm

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.
Ami ekhono shopno dekhi...
HomePage

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Re: 176 - City Navigation

Post by yiuyuho » Fri Jun 13, 2008 8:24 pm

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 176 - City Navigation

Post by Jan » Fri Jun 13, 2008 9:28 pm

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.
Ami ekhono shopno dekhi...
HomePage

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Re: 176 - City Navigation

Post by yiuyuho » Fri Jun 13, 2008 9:49 pm

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?

amantzaris
New poster
Posts: 1
Joined: Thu Nov 20, 2008 11:21 pm

Post by amantzaris » Thu Nov 20, 2008 11:44 pm

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

Post Reply

Return to “Volume 1 (100-199)”