結果

問題 No.1501 酔歩
ユーザー lam6er
提出日時 2025-04-15 22:09:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,732 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 81,652 KB
実行使用メモリ 81,732 KB
最終ジャッジ日時 2025-04-15 22:11:17
合計ジャッジ時間 5,781 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N
    
    if K == 1:
        print(0)
        return
    if K == N:
        print("1")
        return
    
    # Compute sum_total (sum from j=2 to N of 1/(A[j-1] * A[j]))
    sum_total_p = 0
    sum_total_q = 1
    for i in range(1, N):  # j runs from 2 to N (1-based), i is 1-based in 0..N-1
        a = A[i-1]
        b = A[i]
        # term is 1/(a*b)
        term_p = 1
        term_q = a * b
        # sum_total += term
        # sum_total_p/sum_total_q + term_p/term_q
        new_p = sum_total_p * term_q + sum_total_q * term_p
        new_q = sum_total_q * term_q
        g = math.gcd(new_p, new_q)
        sum_total_p = new_p // g
        sum_total_q = new_q // g
    
    # Compute sum_k (sum from j=2 to K of 1/(A[j-1] * A[j]))
    sum_k_p = 0
    sum_k_q = 1
    for i in range(1, K):  # j runs from 2 to K (1-based), i is 1-based in 0..K-1
        a = A[i-1]
        b = A[i]
        term_p = 1
        term_q = a * b
        new_p = sum_k_p * term_q + sum_k_q * term_p
        new_q = sum_k_q * term_q
        g = math.gcd(new_p, new_q)
        sum_k_p = new_p // g
        sum_k_q = new_q // g
    
    # Compute probability = sum_k / sum_total
    numerator = sum_k_p * sum_total_q
    denominator = sum_k_q * sum_total_p
    if denominator == 0:
        print(0)
        return
    g = math.gcd(numerator, denominator)
    numerator //= g
    denominator //= g
    
    if numerator == 0:
        print(0)
    else:
        print(f"{numerator}/{denominator}")

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