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



Sample input:
2 2 50
30 50 1
30 50 2


Sample output:
0.28770000
0.71230000

Submission status: Wrong Answer

Solution code:
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)

def inv(x):
    return pow(x, mod - 2, mod)

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 % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    nm[key] = r * inv(d) % mod
    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:
        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
        for j in range(m+1):
            tr = rs[i][j]
            tt = ts[i][j] + eps
            for k in range(n):
                if i == k:
                    continue
                bi = bisect.bisect_left(ts[k], tt)
                if bi > 0:
                    tr *= 1 - us[k][bi-1]
            r += tr
        rr.append(r)

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


print(main())

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
#!/usr/bin/env 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

Submission status: Accepted

Solution code:
#!/usr/bin/env 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

Submission status: Accepted

Solution code:

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)

Submission status: Runtime Error

Solution code:
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:
        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
        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:
                    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())

Submission status: Runtime Error

Solution code:
def upper_bound(arr, v)
  l = -1
  r = arr.size
  while l + 1 < r
    m = (l + r) / 2
    if arr[m] <= v then l = m
    else r = m
    end
  end
  r
end

EPS = 1e-9
Factorial = (1..50).each_with_object([1]) { |i, arr| arr << arr[-1] * i }

n, m, l = gets.split.map(&:to_i)
p, t, v = n.times.map{ gets.split.map(&:to_i) }.transpose
time_set = n.times.map{ [0] * (m + 1) }
prob_set = n.times.map{ [0] * (m + 1) }
n.times do |i|
  s = v[i] == 0 ? Float::INFINITY : l / v[i].to_f
  (m + 1).times do |j|
    time_set[i][j] = s + t[i] * j
    prob_set[i][j] = (p[i] / 100.0) ** j * (1 - p[i] / 100.0) ** (m - j) * Factorial[m] / Factorial[m - j] / Factorial[j]
  end
end

n.times do |i|
  ret = 0
  (m + 1).times do |j|
    prob = prob_set[i][j]
    n.times do |k|
      next if i == k
      idx = upper_bound(time_set[k], time_set[i][j] + EPS)
      if idx == m + 1
        prob = 0
        break
      end
      prob *= prob_set[k][idx..-1].reduce(:+)
    end
    ret += prob
  end
  puts '%.8f' % ret
end

Submission status: Runtime Error

Solution code:
#!/usr/bin/env 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(MC[k] * (P ** k) * ((100 - P) ** (M - k)))
    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
    ans = float(ans) / 100 ** (N * M)
    print ans