176 - City Navigation
Moderator: Board moderators
176 - City Navigation
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
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
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.
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.
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.
Hi,
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).Basically, ignore houses and consider every driveway as distinct (even if they do go to the same house).
176 City Navigation. WA but it needs rejudge.
I found a program which produces incorrect result but got AC. Here is my testing data:
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:
(A)
(B)
(C)
I hope you understand my drawings. 
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
#
Code: Select all
-1
333
(Program crashed)
Code: Select all
0
261
2
Also, I don't understand the following statements in the question:
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?# 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.
(A)
Code: Select all
A49
--------------
| ____ ____
| | | | |
| | | | |
| ---- ----
| ____ ____
| | | | |
Code: Select all
A49 A48
--------------
| ____ ____
| | | | |
| | | | |
| ---- ----
| ____ ____
| | | | |
Code: Select all
A49
--------------
|______ ____
| | | | |
| | | | |
|------ ----
|______ ____
| | | | |

Does anyone help to confirm the input/output?
For the clarification part, I used the following input to test the AC program:
For the clarification part, I used the following input to test the AC program:
Code: Select all
Code removed ..
- 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.
That should be correct. I can't add any test case since it's not a multiple input program.rickyliu wrote:Code: Select all
A49 -------------- | ____ ____ | | | | | | | | | | | ---- ---- | ____ ____ | | | | |
DON'T PM ME --> For any doubt, suggestion or error reporting, please use the "Contact us" form in the web.
Re: 176 - City Navigation
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.
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.
Ami ekhono shopno dekhi...
HomePage
HomePage
Re: 176 - City Navigation
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).
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
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.
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
HomePage
Re: 176 - City Navigation
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?
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?
-
- New poster
- Posts: 1
- Joined: Thu Nov 20, 2008 11:21 pm