結果
問題 | No.2067 ±2^k operations |
ユーザー |
![]() |
提出日時 | 2022-08-25 21:51:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,100 ms / 2,000 ms |
コード長 | 590 bytes |
コンパイル時間 | 259 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 259,172 KB |
最終ジャッジ日時 | 2024-10-15 20:05:49 |
合計ジャッジ時間 | 15,210 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 23 |
ソースコード
memo={}def f(n):if n<=1:return nif n in memo:return memo[n]if n%2==0:res=f(n//2)memo[n]=resreturn reselse:res=1+min(f(n//2),f(n//2+1))memo[n]=resreturn resdef calc(n):if n==1:return 0,1,0,0if n%4==0:res,a,b,c=calc(n//4)res2=res*4+4*a+3*b+ca2=2*a+b+cb2=a+2*b+cc2=a+b+2*creturn res2,a2,b2,c2res,a,b,c=calc(n-1)p=f(n-1)q=f(n)res+=pif p<q:a+=1if p==q:b+=1if p>q:c+=1return res,a,b,cfor _ in range(int(input())):n=int(input())print(calc(n+1)[0])