Problem:
Marathon Match  N people run a marathon.
There are M resting places on the way.
For each resting place, the i -th runner takes a break with probability P_i percent.
When the i -th runner takes a break,  he gets rest for T_i time. The i -th runner runs at constant speed V_i , and
the  distance of the marathon is L . You are requested to compute the probability  for each runner to win the first place.
If a runner arrives at the goal with another person at the same time, they are not considered to win the first place. Input A dataset is given in the following format:  N  M  L  P_1  T_1  V_1  P_2  T_2  V_2  ...  P_N  T_N  V_N  The first line of a dataset contains three integers N ( 1 \leq N \leq 100 ), M ( 0 \leq M \leq 50 ) and L ( 1 \leq L \leq 100,000 ). N is the number of runners. M is the number of resting places. L is the  distance of the marathon. Each of the following N lines contains three integers P_i ( 0 \leq P_i \leq 100 ), T_i ( 0 \leq T_i \leq 100 ) and V_i ( 0 \leq V_i \leq 100 ) describing the i -th runner. P_i is the probability to take a break. T_i is the time of resting. V_i is the speed. Output For each runner, you should answer the probability of winning.
The i -th line in the output should be the probability that the i -th runner wins the marathon.
Each number in the output should not contain an error greater than 10^{-5} . Sample Input 1 2 2 50
30 50 1
30 50 2 Output for the Sample Input 1 0.28770000
0.71230000 Sample Input 2 2 1 100
100 100 10
0 100 1 Output for the Sample Input 2 0.00000000
1.00000000 Sample Input 3 3 1 100
50 1 1
50 1 1
50 1 1 Output for the Sample Input 3 0.12500000
0.12500000
0.12500000 Sample Input 4 2 2 50
30 0 1
30 50 2 Output for the Sample Input 4 0.51000000
0.49000000

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


nm = {}
def nCr(n, b):
    if b > n - b:
        b = n - b
    key = (n,b)
    if key in nm:
        return nm[key]
    r = 1
    for k in range(n, n-b, -1):
        r = r * k
    d = 1
    for k in range(1, b+1):
        d = d * k
    nm[key] = r / d
    return nm[key]


def main():
    rr = []

    n,m,l = LI()
    ps = [LI() for _ in range(n)]
    ts = []
    rs = []
    us = []

    for p,t,v in ps:
        if v == 0:
            ts.append(0)
            rs.append(0)
            us.append(0)
            continue
        p /= 100
        u = l / v
        ti = []
        ri = []
        for i in range(m+1):
            ti.append(u+t*i)
            k = pow(1-p, m-i) * pow(p, i) * nCr(m, i)
            ri.append(k)
        ts.append(ti)
        rs.append(ri)
        ui = ri[:]
        for i in range(1,m+1):
            ui[i] += ui[i-1]
        us.append(ui)

    for i in range(n):
        r = 0
        if ts[i] == 0:
            rr.append(r)
            continue
        for j in range(m+1):
            tr = rs[i][j]
            tt = ts[i][j] + 1.0 / 10**10
            for k in range(n):
                if i == k or ts[k] == 0:
                    continue
                bi = bisect.bisect_left(ts[k], tt)
                if bi > 0:
                    tr *= 1 - us[k][bi-1]
            r += tr
        rr.append('{:.9f}'.format(r))

    return '\n'.join(map(str,rr))


print(main())

Solution (Python):


from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

N, M, L = map(int, raw_input().split())

def fact(n):
    if n <= 1:
        return 1
    return fact(n - 1) * n
MC = []
for i in range(M + 1):
    MC.append(fact(M) / fact(i) / fact(M - i))

p_lst = []
P_val = []
P_sum = []

for i in range(N):
    P, T, V = map(int, raw_input().split())
    p_lst.append((T, V))
    PP = []
    for k in range(M + 1):
        PP.append(float(MC[k] * (P ** k) * ((100 - P) ** (M - k))) / 100 ** M)
    P_val.append(list(PP))
    for k in range(M, 0, -1):
        PP[k - 1] += PP[k]
    P_sum.append(PP)

def comp(p1, p2, k1, k2):
    T1, V1 = p1
    T2, V2 = p2
    return L * (V2 - V1) < V1 * V2 * (k2 * T2 - k1 * T1)

for i in range(N):
    ans = 0
    index_lst = [0 for j in range(N)]
    for k1 in range(M + 1):
        ret = P_val[i][k1]
        for j in range(N):
            if i == j:
                continue
            flag = True
            while True:
                k2 = index_lst[j]
                if k2 > M:
                    ret *= 0
                    break
                if comp(p_lst[i], p_lst[j], k1, k2):
                    ret *= P_sum[j][k2]
                    break
                index_lst[j] += 1
        ans += ret
    print '%.10f' % ans

Solution (Python):


from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

N, M, L = map(int, raw_input().split())

def fact(n):
    if n <= 1:
        return 1
    return fact(n - 1) * n
MC = []
for i in range(M + 1):
    MC.append(fact(M) / fact(i) / fact(M - i))

p_lst = []
P_val = []
P_sum = []

for i in range(N):
    P, T, V = map(int, raw_input().split())
    p_lst.append((T, V))
    PP = []
    for k in range(M + 1):
        PP.append(float(MC[k] * (P ** k) * ((100 - P) ** (M - k))) / 100 ** M)
    P_val.append(list(PP))
    for k in range(M, 0, -1):
        PP[k - 1] += PP[k]
    P_sum.append(PP)

def comp(p1, p2, k1, k2):
    T1, V1 = p1
    T2, V2 = p2
    return L * (V2 - V1) < V1 * V2 * (k2 * T2 - k1 * T1)

for i in range(N):
    ans = 0
    index_lst = [0 for j in range(N)]
    for k1 in range(M + 1):
        ret = P_val[i][k1]
        for j in range(N):
            if i == j:
                continue
            while True:
                k2 = index_lst[j]
                if k2 > M:
                    ret *= 0
                    break
                if comp(p_lst[i], p_lst[j], k1, k2):
                    ret *= P_sum[j][k2]
                    break
                index_lst[j] += 1
        ans += ret
    print '%.10f' % ans

Solution (Python):

import bisect
def nCr(n, r):
    r = min(r, n-r)
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i
    return numerator // denominator

n,m,l=map(int,input().split())
data = [[0 for i in range(m+1)]for i in range(n)]
for i in range(n):
    p,t,v=map(int,input().split())
    for j in range(m+1):
        data[i][j]=((t*j+l/v)if v!=0 else 9999999999999999, (p/100.0)**(j) * nCr(m,j) * (1-p/100.0)**(m-j))

ans=[]
for i in range(n):
    win=0
    for j in range(m+1):
        wintmp=data[i][j][1]
        for x in range(n):
            if i==x:
                continue
            tmp=0
            for a,b in data[x][bisect.bisect_right(data[x],(data[i][j][0],5)):]:
                tmp+=b
            wintmp*=tmp
        win+=wintmp
    ans.append(win)

for a in ans:
    print('%.8f'%a)