結果
問題 | No.1501 酔歩 |
ユーザー | shotoyoo |
提出日時 | 2021-05-07 22:34:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 701 ms / 2,000 ms |
コード長 | 974 bytes |
コンパイル時間 | 274 ms |
コンパイル使用メモリ | 87,100 KB |
実行使用メモリ | 124,124 KB |
最終ジャッジ日時 | 2023-10-13 13:52:55 |
合計ジャッジ時間 | 30,782 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 227 ms
89,548 KB |
testcase_01 | AC | 222 ms
89,572 KB |
testcase_02 | AC | 222 ms
89,532 KB |
testcase_03 | AC | 224 ms
89,364 KB |
testcase_04 | AC | 219 ms
89,484 KB |
testcase_05 | AC | 607 ms
115,792 KB |
testcase_06 | AC | 529 ms
109,940 KB |
testcase_07 | AC | 583 ms
114,924 KB |
testcase_08 | AC | 375 ms
96,600 KB |
testcase_09 | AC | 556 ms
112,776 KB |
testcase_10 | AC | 416 ms
99,608 KB |
testcase_11 | AC | 533 ms
109,556 KB |
testcase_12 | AC | 481 ms
105,364 KB |
testcase_13 | AC | 220 ms
89,360 KB |
testcase_14 | AC | 222 ms
89,560 KB |
testcase_15 | AC | 219 ms
89,512 KB |
testcase_16 | AC | 223 ms
89,672 KB |
testcase_17 | AC | 218 ms
89,644 KB |
testcase_18 | AC | 218 ms
89,368 KB |
testcase_19 | AC | 221 ms
89,280 KB |
testcase_20 | AC | 220 ms
89,472 KB |
testcase_21 | AC | 225 ms
89,368 KB |
testcase_22 | AC | 687 ms
123,312 KB |
testcase_23 | AC | 687 ms
123,372 KB |
testcase_24 | AC | 684 ms
123,272 KB |
testcase_25 | AC | 690 ms
123,004 KB |
testcase_26 | AC | 675 ms
124,012 KB |
testcase_27 | AC | 687 ms
123,448 KB |
testcase_28 | AC | 690 ms
123,528 KB |
testcase_29 | AC | 675 ms
123,308 KB |
testcase_30 | AC | 694 ms
123,496 KB |
testcase_31 | AC | 671 ms
123,948 KB |
testcase_32 | AC | 694 ms
122,984 KB |
testcase_33 | AC | 701 ms
122,948 KB |
testcase_34 | AC | 689 ms
123,984 KB |
testcase_35 | AC | 680 ms
124,124 KB |
testcase_36 | AC | 676 ms
123,412 KB |
testcase_37 | AC | 672 ms
123,412 KB |
testcase_38 | AC | 683 ms
123,280 KB |
testcase_39 | AC | 687 ms
122,980 KB |
testcase_40 | AC | 690 ms
123,572 KB |
testcase_41 | AC | 684 ms
123,748 KB |
testcase_42 | AC | 596 ms
123,704 KB |
testcase_43 | AC | 228 ms
89,528 KB |
testcase_44 | AC | 222 ms
89,580 KB |
testcase_45 | AC | 623 ms
123,892 KB |
testcase_46 | AC | 582 ms
123,804 KB |
testcase_47 | AC | 596 ms
123,880 KB |
testcase_48 | AC | 639 ms
123,420 KB |
testcase_49 | AC | 644 ms
123,536 KB |
testcase_50 | AC | 634 ms
123,544 KB |
testcase_51 | AC | 653 ms
124,096 KB |
testcase_52 | AC | 638 ms
123,540 KB |
testcase_53 | AC | 224 ms
89,692 KB |
testcase_54 | AC | 219 ms
89,528 KB |
testcase_55 | AC | 218 ms
89,228 KB |
ソースコード
import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(2*10**5+10) write = lambda x: sys.stdout.write(x+"\n") debug = lambda x: sys.stderr.write(x+"\n") from fractions import Fraction as f n,k = list(map(int, input().split())) a = list(map(int, input().split())) if n==1: ans = 1,1 elif n==2: if k==2: ans = 1,1 else: ans = 0,1 else: if k==1: ans = 0,1 elif k==n: ans = 1,1 else: s = [0,1] t = [0,0] for i in range(n-2): a0,a1 = a[i],a[i+2] ns = f((a0+a1)*s[-1] - a0*s[-2], a1) nt = f((a0+a1)*t[-1] - a0*t[-2], a1) s.append(ns) t.append(nt) val = f(1-t[-1], s[-1]) val = val * s[k-1] + t[k-1] ans = val.numerator, val.denominator if ans[0]==0: print(0) else: from math import gcd g = gcd(ans[0], ans[1]) ans = [ans[0]//g, ans[1]//g] print("/".join(map(str, ans)))