結果

問題 No.813 ユキちゃんの冒険
ユーザー qwewe
提出日時 2025-04-24 12:32:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,455 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 89,948 KB
最終ジャッジ日時 2025-04-24 12:34:13
合計ジャッジ時間 5,575 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    p = float(input[idx])
    idx += 1
    q = float(input[idx])
    
    # Initialize right and left arrays with 1-based indexing
    right = [0.0] * (N + 2)  # right[i]: probability of being at gate i facing right
    left = [0.0] * (N + 2)   # left[i]: probability of being at gate i facing left
    right[1] = 1.0  # start at gate 1 facing right
    
    r = 0.0  # Accumulated probability of returning to origin
    eps = 1e-15  # Convergence threshold
    max_iterations = 1000000  # Prevent infinite loop
    
    for _ in range(max_iterations):
        right_new = [0.0] * (N + 2)
        left_new = [0.0] * (N + 2)
        add_r = 0.0
        
        for i in range(1, N + 1):
            # Process right-facing at gate i
            current_r = right[i]
            if current_r > eps:
                # Probability p: reverse direction (left)
                new_i = i - 1
                if new_i == 0:
                    add_r += p * current_r
                elif new_i >= 1:
                    left_new[new_i] += p * current_r
                # Probability q: continue right
                new_i = i + 1
                if new_i == 0:
                    add_r += q * current_r
                elif new_i <= N:
                    right_new[new_i] += q * current_r
            
            # Process left-facing at gate i
            current_l = left[i]
            if current_l > eps:
                # Probability p: reverse direction (right)
                new_i = i + 1
                if new_i == 0:
                    add_r += p * current_l
                elif new_i <= N:
                    right_new[new_i] += p * current_l
                # Probability q: continue left
                new_i = i - 1
                if new_i == 0:
                    add_r += q * current_l
                elif new_i >= 1:
                    left_new[new_i] += q * current_l
        
        r += add_r
        
        # Check for convergence
        sum_new = sum(right_new) + sum(left_new)
        if sum_new < eps:
            break
        
        # Update right and left arrays for next iteration
        right, right_new = right_new, right
        left, left_new = left_new, left
    
    print("{0:.15f}".format(r).rstrip('0').rstrip('.') if '.' in "{0:.15f}".format(r) else r)

if __name__ == "__main__":
    main()
0