Участник:Andriygav/REPAIR1

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/REPAIR1

import math
 
def f(m, B, p):
    q = 1-p
    qm = q**m
 
    if m <= 1:
        return 0.0
 
    return (B/p)*((m-1)*p*(1-qm)-q*(1-m*qm/q+(m-1)*qm))
 
def find(m, A, B, p, epsilon = 1e-13):
    a = [0]*(m+1)
    b = [0]*(m+1)
 
    for k in range(1, m+1):
        tmp = min(a[k-1], b[k-1]+A)
        if abs(tmp-b[k-1]-A) < epsilon:
            return k-1, 
        a[k] = B+epsilon
        b[k] = (1-p)*b[k-1]+p*tmp
 
    return m
 
def dp(m, A, B, p, epsilon = 1e-13):
    a = [0]*(m+1)
    b = [0]*(m+1)
 
    for k in range(1, m+1):
        tmp = min(a[k-1], b[k-1]+A)
        a[k] = B+tmp
        b[k] = (1-p)*b[k-1]+p*tmp
 
    return b[m]
 
 
def solver(n, p, A, B, epsilon = 1e-13):
    answer = 0.0
    if abs(p) < epsilon or (abs(A) < epsilon and abs(B) < epsilon):
        answer = 0.0
    elif abs(p-1) < epsilon:
        answer = (n-1)*(A if A < B else B)
    elif B < p*A + epsilon:
        answer = f(n, B, p)
    else:
        m = math.floor(math.log(1-p*A/B)/math.log(1-p)+epsilon)
 
        m = find(m, A, B, p, epsilon) + 1
 
        if n <= m:
            answer = f(n, B, p)
        elif m <= 10:
            answer = p*A*(n-m)+dp(m, A, B, p, epsilon)
        else:
            answer = p*A*(n-m)+f(m, B, p)
 
    return float(answer)
 
answers = []
while True:
    N, P, A, B = list(map(int, input().split()))
    if N == 0 and P == 0 and A == 0 and B == 0:
        break
    else:
        answers.append('%.4f' % solver(N, P/100.0, A, B, epsilon = 1e-6))
 
print('\n'.join(answers))