cp2.2

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 13 17:27:11 2014

@author: Administrator
"""

# 2.2.1
def coinproblem(c, a):
    coins = [1, 5, 10, 50, 100, 500]
    cnt = 0
    for x, y in zip(coins, c)[::-1]:
        num = min(a / x, y)
        a -= num * x
        cnt += num
    return cnt
    
# 2.2.2
def section(n, s, t):
    cnt = cft = 0
    for ft, st in sorted(zip(t, s)):
        if st > cft:
            cnt += 1
            cft = ft
    return cnt
    
# 2.2.3
def poj3617(n, s):
    rt = [0] * n
    st, ed = 0, n-1
    for pos in xrange(n):
        if s[st] < s[ed]:
            rt[pos] = s[st]
            st += 1
        else:
            rt[pos] = s[ed]
            ed -= 1
    return ''.join(rt)
    
#2.2.4
from itertools import tee
def poj3069(n, r, x):
    cnt, crt_not = 1, x[0]
    itrS, itrN = tee(enumerate(x))
    for i, ix in itrS:
        if ix > crt_not + r:
            crt_s = x[i-1]
            try:
                crt_not = next(x_ for _, x_ in itrN if x_ > crt_s + r)
                cnt += 1
            except StopIteration:
                pass
    return cnt