Google Code Jam 2011 Round1B B. Revenge of the Hot Dogs

Revenge of the Hot Dogs

位置PにV個のホットドッグ屋がある時、それらを間隔Dで並べてさらに他のグループとも間隔Dなので、V*Dの幅の板を重ならないように、かつなるべく元の位置から動かさないように敷き詰めるイメージ。秒数が与えられたなら、なるべく左端に寄せて置いていくことが最善で、敷き詰めが可能かどうか判定できる。秒数を変えながら二分探索。DとPを倍にしておくと整数のまま計算できる。

class empty: pass;

def check(C,D,V,t):
    p = -(10**100)
    for v in V:
        w = D*v.V
        r = t - D*(v.V-1)/2
        if r<0 or p+w/2-v.P>r:
            return False
        p = max(v.P-r+w/2,p+w)
    return True

T = input()
for case in range(1,T+1):
    C,D = map(int,raw_input().split())
    D *= 2
    V = []
    for i in range(C):
        t = map(int,raw_input().split())
        V += [empty()]
        V[-1].P = t[0]*2
        V[-1].V = t[1]
    
    l = 0
    r = 10**100
    while (r-l>1):
        m = (l+r)/2
        if check(C,D,V,m):
            r = m
        else:
            l = m
    if check(C,D,V,0):
        r = 0
    print "Case #%s: %.1f" % (case,r*0.5)