10671 - Grid Speed

[Examiner]

I have some difficulty with the second sample test case. My program reports it is possible to travel, and I have to agree!

My diagram looks like this

Code: Select all

8) 20          /--<--S
7) 10          |
6) 20          |
5) 10          |
4) 30    T--<--/
3) 20
2) 20
1) 10
      10 20 20 30 10 20 10 10
      1) 2) 3) 4) 5) 6) 7) 8)

Going along the route indicted above at maximum speed takes

• time
  = 2 / 30 * 60 * 6 + 2 / 20 * 60 * 2
  = 24 + 12
  = 36,
  
  10 <= time <= 39.

It seems possible to travel within the time limits. Anything wrong? Is it because the vertical time limits are put in reverse order?

[Adrian Kuegel]

Your diagram is wrong.
The values of the horizontal streets are given first, then the values of the vertical streets.

Code: Select all

8) 10          /--<--S
7) 10          |
6) 20          |
5) 10          |
4) 30    T--<--/
3) 20
2) 20
1) 10
      10 20 20 30 10 20 10 20
      1) 2) 3) 4) 5) 6) 7) 8)

so your route needs 48 minutes.

[Ghost77 dimen]

I think it is an ordinary dp problem, pass it without further doubt.

What I'd like to ask here is how to reduce the memory and time as

low as the top of the rankist.

Before posting, I tried to find somthing out.

Memory.

1. reduce the 2-dim mem to 1-dim mem. (mine: done)

2. Try linked list instead of ordinary array. (mine: no)

3. replace double with float? (mine: no)

Even used the above method, the mem still much higher than that,

besides you should risk something.

Time.

1. If you use the linked list, maybe the needed time will be a little lower.

2. the unit time (1min=?Ticks). I let the 1min=210Ticks

maybe someone have better way than this.

Any opinion is welcome.