結果

問題 No.1501 酔歩
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:52:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,408 bytes
コンパイル時間 1,946 ms
コンパイル使用メモリ 81,160 KB
実行使用メモリ 89,920 KB
最終ジャッジ日時 2025-04-16 15:53:03
合計ジャッジ時間 6,404 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    if K == 1:
        print("0")
        return
    if K == N:
        print("1")
        return
    
    max_i = N - 1
    num = [0] * (max_i + 2)  # 1-based indexing
    den = [0] * (max_i + 2)
    
    for i in range(2, max_i + 1):
        # Convert to 0-based index for A
        if i - 2 < 0:
            A_i_minus_1 = 0
        else:
            A_i_minus_1 = A[i - 2]
        A_i_plus_1 = A[i]
        
        if i - 1 >= 2:
            prev_num = num[i - 1]
            prev_den = den[i - 1]
        else:
            # For i=2, previous is i=1 which is not processed
            prev_num = 0
            prev_den = 1
        
        denominator_part = (A_i_minus_1 + A_i_plus_1) * prev_den - A_i_minus_1 * prev_num
        numerator_i = A_i_plus_1 * prev_den
        
        g = math.gcd(numerator_i, denominator_part)
        num[i] = numerator_i // g
        den[i] = denominator_part // g
    
    p_num = 1
    p_den = 1
    for i in range(K, max_i + 1):
        a_num = num[i]
        a_den = den[i]
        p_num *= a_num
        p_den *= a_den
        g = math.gcd(p_num, p_den)
        p_num //= g
        p_den //= g
    
    if p_num == 0:
        print("0")
    else:
        print(f"{p_num}/{p_den}")

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