結果
問題 | No.1869 Doubling? |
ユーザー |
![]() |
提出日時 | 2022-03-11 22:05:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 1,566 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 51,968 KB |
最終ジャッジ日時 | 2024-09-16 02:22:35 |
合計ジャッジ時間 | 3,747 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
N,M=map(int,input().split()) #一番うしろが一番大きくなる。 #N=10**9なので実際にAを構成することはできない #A[i-1]=A[i]/2 or (A[i]+1)/2なので、実はA[i]が決まればA[i-1]はユニークに決まる。よってA[N-1]を決め打ちして、前までさかのぼってA[1]=1となるようなもののうちA[N-1]の最大を探す #A[N-1]=Mからスタートして1になるまで繰り返す。1になるまでにAが全部完成すればNをへらす。 #途中で1になるならそれでおわる。半分ずつになるのでO(log(N))程度の時間で終わるはず #A[N-1]=xとして、A[1]=1になるかどうか。これはO(log(N)) def C(x): cnt=0 while x!=1: cnt+=1 if x%2==0: x//=2 else: x=(x+1)//2 if cnt<N: #N回いないにできるならA[1]=1 return True else: return False #2分探索 #最初Mは超えないようにleft,rightを設定します left=0 right=M+1 while right-left>1: mid=left+(right-left)//2 if C(mid): #TrueならもっとふやしてもOK left=mid else: right=mid #A[-1]=leftで確定なので、このときの和を求めます n=left les=n #cntはlesに後ろからcnt項ぶんたされたことを示す。最初にnをいれておくとN,M=1でもOKになるのでね。 cnt=1 #1になるまでループ while n!=1: if n%2==0: n//=2 else: n=(n+1)//2 les+=n cnt+=1 if cnt>=N: #Nを超えたらbreak break if cnt>=N: #この場合はこれで終わりです。 print(les) else: #この場合は残りの1を足す print(les+(N-cnt))