Roadside Trees (Simplified Edition) (Codeforces 265B)
Tags: Implement, greedy

Squirrel Liss loves nuts. There are n trees (numbered 1 to n from west to east) along a street and there is a delicious nut on the top of each tree. The height of the tree i is hi. Liss wants to eat all nuts.Now Liss is on the root of the tree with the number 1. In one second Liss can perform one of the following actions:  Walk up or down one unit on a tree.  Eat a nut on the top of the current tree.  Jump to the next tree. In this action the height of Liss doesn't change. More formally, when Liss is at height h of the tree i (1 ≤ i ≤ n - 1), she jumps to height h of the tree i + 1. This action can't be performed if h > hi + 1. Compute the minimal time (in seconds) required to eat all nuts.

Input: The first line contains an integer n (1  ≤  n ≤ 105) — the number of trees.Next n lines contains the height of trees: i-th line contains an integer hi (1 ≤ hi ≤ 104) — the height of the tree with the number i.

Output: Print a single integer — the minimal time required to eat all nuts in seconds.


Sample Inputs:
2
1
2

5
2
1
2
1
1

Sample Outputs:
5

14

Solution (Python):
import math
import sys
cin = lambda : sys.stdin.readline().rstrip('\r\n')
cout = lambda x: sys.stdout.write(str(x))
ans = 0
l = [int(cin()) for _ in range(int(cin()))]
ans = l[0] + 1
for i in range(1, len(l)):
    if l[i - 1] > l[i]:
        ans += l[i - 1] - l[i]
        ans += 2
    else:
        ans += 2
        ans += l[i] - l[i - 1]
print(ans)

Solution (Python):
import bisect
from sys import stdin
input = stdin.readline
mod = 10 ** 9 + 7
eps = 10 ** (-9)

def linp(type=int):
    return list(map(type, input().split()))

def minp(type=int):
    return map(type, input().split())

def tinp(type=int):
    return type(input())

def __gcd(a, b):
    return a if b == 0 else __gcd(b, a % b)

def __lcm(a, b):
    return a * b / __gcd(a, b)

def __fact(n):
    return 1 if n == 1 else n * __fact(n - 1)

def __mex(a):
    mex = 0
    a.sort()
    for x in a:
        if x <= mex:
            mex += 1
        else:
            break
    return mex

def __dist(x1, y1, x2, y2):
    return (x1 - x2) ** 2 + (y1 - y2) ** 2

def __getprimes(n):
    isprime = [True for i in range(n + 1)]
    primes = []
    for i in range(2, n + 1):
        if isprime[i]:
            for j in range(i * i, n + 1, i):
                isprime[j] = False
    for i in range(2, n + 1):
        if isprime[i]:
            primes.append(i)
    return primes

def __getdividers(n):
    i = 1
    ret = []
    while i * i <= n:
        if n % i == 0:
            ret.append(i)
            if i * i != n:
                ret.append(n // i)
        i += 1
    ret.sort()
    return ret

def __modInverse(a, m):
    m0 = m
    y = 0
    x = 1
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t
    if x < 0:
        x = x + m0
    return x

def __isprime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def __cntprimediv(n):
    ret = 0
    x = n
    i = 2
    while i * i <= x:
        while n % i == 0:
            n //= i
            ret += 1
        i += 1
    if n > 1:
        ret += 1
    return ret

def __primefactors(n):
    ret = []
    x = n
    i = 2
    while i * i <= x:
        while n % i == 0:
            ret.append(i)
            n //= i
        i += 1
    if n > 1:
        ret.append(n)
    return ret

def __sumdigit(n):
    ret = 0
    while n > 0:
        ret += n % 10
        n //= 10
    return ret

def __zfunc(s):
    n = len(s)
    z = [0 for i in range(n)]
    l = 0
    r = 0
    for i in range(1, n):
        if r >= i:
            z[i] = min(z[i - l], r - i + 1)
        while z[i] + i < n and s[z[i]] == s[z[i] + i]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

def __to(n, x):
    ret = ''
    while n > 0:
        q = n % x
        if q < 10:
            ret += str(q)
        else:
            ret += chr(q - 10 + ord('a'))
        n //= x
    return ret[::-1]

def solve(t_id):
    n = tinp()
    ans = 2 * n - 1
    cur = 0
    while n > 0:
        x = tinp()
        ans += abs(cur - x)
        cur = x
        n -= 1
    print(ans)
tc = 1
for i in range(tc):
    solve(i + 1)

Solution (Python):
import sys
input = sys.stdin.readline
(c, h) = (0, 0)
k = int(input())
for _ in range(k):
    n = int(input())
    c += abs(n - h) + 1
    h += n - h
print(c + k - 1)