Codeforces Beta Round #50 C. First Digit Law

First Digit Law

先頭が1である確率は[L,R]の範囲内で先頭が1であるものの個数を(R-L+1)で割れば求まる。ちょうどk個が1である確率を動的計画法で求めて足しあわせる。10¹⁸は入るけど、10¹⁹はsigned long longから溢れる。Pythonだとそういうことを気にしなくて良いので楽。

N = input()
T = [1]+[0]*N
for i in range(N):
    L,R = map(int,raw_input().split())
    c = 1
    n = 0
    while c<=10**18:
        n += max(0,min(R,2*c-1)-max(L,c)+1)
        c *= 10
    p = float(n)/(R-L+1)
    
    B = T
    T = [B[0]*(1-p)]+[0]*N
    for j in range(1,N+1):
        T[j] = B[j]*(1-p)+B[j-1]*p

K = input()
print "%.16f"%sum(T[(N*K+99)/100:])