結果

問題 No.1501 酔歩
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:26:24
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,184 bytes
コンパイル時間 262 ms
コンパイル使用メモリ 82,028 KB
実行使用メモリ 80,400 KB
最終ジャッジ日時 2025-06-12 21:27:46
合計ジャッジ時間 6,002 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    K = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    
    if K == 1:
        print(0)
        return
    if K == N:
        print(1)
        return
    
    # Compute sum_S (sum from k=3 to N)
    sum_S_num = 0
    sum_S_den = 1
    for k in range(3, N+1):
        a_prev = A[k-2]  # 0-based index
        a_curr = A[k-1]  # 0-based index
        Tk_num = 1
        Tk_den = a_prev * a_curr
        
        # Add Tk to sum_S
        numerator = sum_S_num * Tk_den + Tk_num * sum_S_den
        denominator = sum_S_den * Tk_den
        
        g = math.gcd(numerator, denominator)
        sum_S_num = numerator // g
        sum_S_den = denominator // g
    
    # Compute sum_SK (sum from k=3 to K)
    sum_SK_num = 0
    sum_SK_den = 1
    for k in range(3, K+1):
        a_prev = A[k-2]  # 0-based index
        a_curr = A[k-1]  # 0-based index
        Tk_num = 1
        Tk_den = a_prev * a_curr
        
        # Add Tk to sum_SK
        numerator = sum_SK_num * Tk_den + Tk_num * sum_SK_den
        denominator = sum_SK_den * Tk_den
        
        g = math.gcd(numerator, denominator)
        sum_SK_num = numerator // g
        sum_SK_den = denominator // g
    
    A1 = A[0]
    A2 = A[1]
    term = A1 * A2
    
    # Compute C: 1 + term * sum_S
    C_num = 1 * sum_S_den + term * sum_S_num
    C_den = sum_S_den
    g = math.gcd(C_num, C_den)
    C_num = C_num // g
    C_den = C_den // g
    
    # Compute C_K: 1 + term * sum_SK
    CK_num = 1 * sum_SK_den + term * sum_SK_num
    CK_den = sum_SK_den
    g = math.gcd(CK_num, CK_den)
    CK_num = CK_num // g
    CK_den = CK_den // g
    
    # Compute the final probability
    numerator = CK_num * C_den
    denominator = CK_den * C_num
    g = math.gcd(numerator, denominator)
    numerator = numerator // g
    denominator = denominator // g
    
    if denominator == 0:
        print(0)
    else:
        if numerator == 0:
            print(0)
        else:
            print(f"{numerator}/{denominator}")

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