Codeforces: B. Roadside Trees (Simplified Edition)

The problem is from codeforces: http://www.codeforces.com/contest/265/problem/B

This problem is not difficult, but it took me nearly 1:30 hr to get it right during the contest. I thought at first, the man was on the top of the tree, but apparently he was on the ‘root’ of the tree number 1.

No matter what the strategy is, the minimal time includes n seconds of eating a nut and n – 1 seconds of jumping between the trees, so these two parts are fixed.

The rest is just simple, simulation works just as fine. Recording the current height and compare with the next tree height, if it is higher, jump to next tree, otherwise, lower the height (which takes the seconds as the height difference).

#!/usr/bin/env python

n = int(raw_input())
h = []

for i in xrange(n):
    h.append(int(raw_input()))

s = n + n - 1
curh = 0

for i in xrange(n):
    x = h[i]
    if curh < x:
        s += x - curh
    else:
        s += curh - x
    curh = x

print s

This is the greedy stategy: always jump to the next tree if possible.

–EOF (The Ultimate Computing & Technology Blog) —