176 - City Navigation

[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

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

[Abednego]

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

[little joey]

Yes, it should be 98.

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

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

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

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

[Carlos]

Code: Select all

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

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

[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

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

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

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

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

[amantzaris]

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