結果
問題 |
No.1929 Exponential Sequence
|
ユーザー |
👑 ![]() |
提出日時 | 2022-05-06 23:39:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 632 ms / 2,000 ms |
コード長 | 1,196 bytes |
コンパイル時間 | 188 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 139,508 KB |
最終ジャッジ日時 | 2024-09-14 03:54:32 |
合計ジャッジ時間 | 5,919 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 |
ソースコード
def Binary_Search_Small_Count(A, x, equal=False, sort=False): """二分探索によって, x 未満の要素の個数を調べる. A: リスト x: 調べる要素 sort: ソートをする必要があるかどうか (True で必要) equal: True のときは x "未満" が x "以下" になる """ if sort: A.sort() if len(A)==0 or A[0]>x or ((not equal) and A[0]==x): return 0 L,R=0,len(A) while R-L>1: C=L+(R-L)//2 if A[C]<x or (equal and A[C]==x): L=C else: R=C return L+1 #================================================== def f(B): X=[] I=[] for b in B: t=0 while pow(b,t+1)<=S: t+=1 I.append(range(1,t+1)) for P in product(*I): s=0 for b,p in zip(B,P): s+=pow(b,p) if s<=S: X.append(s) X.sort() return X #================================================== from itertools import product N,S=map(int,input().split()) A=list(map(int,input().split())) B=A[:N//2]; C=A[N//2:] X=f(B) Y=f(C) ans=0 for x in X: ans+=Binary_Search_Small_Count(Y, S-x, True) print(ans)