結果
問題 | No.1501 酔歩 |
ユーザー |
|
提出日時 | 2021-05-07 22:24:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 645 ms / 2,000 ms |
コード長 | 1,080 bytes |
コンパイル時間 | 225 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 111,728 KB |
最終ジャッジ日時 | 2024-09-15 10:28:03 |
合計ジャッジ時間 | 25,796 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
#!/usr/bin/env python3 import fractions from typing import * def solve(n: int, k: int, x: List[int]) -> str: if k == n: return 1 a = [None] * (n - 1) b = [None] * (n - 1) a[0] = 0 b[0] = 0 for i in range(1, n - 1): left = fractions.Fraction(x[i - 1], x[i - 1] + x[i + 1]) right = fractions.Fraction(x[i + 1], x[i - 1] + x[i + 1]) a[i] = right / (1 - a[i - 1] * left) b[i] = b[i - 1] * left / (1 - a[i - 1] * left) c = 1 for i in reversed(range(k - 1, n - 1)): c = a[i] * c + b[i] return c # generated by oj-template v4.7.2 (https://github.com/online-judge-tools/template-generator) def main(): import sys tokens = iter(sys.stdin.read().split()) N = int(next(tokens)) K = int(next(tokens)) A = [None for _ in range(N)] for i in range(N): A[i] = int(next(tokens)) assert next(tokens, None) is None a = solve(N, K, A) if a == 0: print(0) elif a == 1: print('1/1') else: print(a) if __name__ == '__main__': main()