結果
問題 |
No.320 眠れない夜に
|
ユーザー |
👑 ![]() |
提出日時 | 2025-07-21 15:19:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 1,814 bytes |
コンパイル時間 | 561 ms |
コンパイル使用メモリ | 82,360 KB |
実行使用メモリ | 54,304 KB |
最終ジャッジ日時 | 2025-07-21 15:19:52 |
合計ジャッジ時間 | 3,469 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
""" https://yukicoder.me/problems/no/320 謎だけどfib進法で表してみる? -1することで、特定の値の倍数に移行全部変化する 枝狩りできるのかなぁ 答を見た。確かにだ... 負の寄与がちゃんとフィボナッチになっていることに気が付かなかったのが敗因 """ import math import sys from sys import stdin """ INF = float("inf") def solve(L,R,idx,cnt): #if M % math.gcd(L,R) != 0: # return INF if idx > N: return INF ret = INF # 正解 nex = L+R if nex == M: ret = min(ret,cnt + (N-idx)) if nex < M: ret = min(ret, solve(R,nex,idx+1,cnt) ) # 不正解 nex = L+R-1 if nex == M: ret = min(ret,cnt+1+(N-idx)) if nex < M: ret = min(ret,solve(R,nex,idx+1,cnt+1)) # print (L,R,idx,cnt,ret) return ret N,M = map(int,input().split()) print (solve(1,2,4,0)) """ fib = [1,1] for i in range(100): fib.append(fib[-1] + fib[-2]) # print (fib) def convert(X,idx): ret = [] for i in range(idx,-1,-1): if X >= fib[i]: ret.append(1) X -= fib[i] else: ret.append(0) ret.reverse() return ret N,M = map(int,input().split()) base = fib[N-1] if base < M: print (-1) else: print ( sum( convert(base-M,N-3)) ) """ for i in range(100): print (i,convert(i)[:10]) N,M = map(int,input().split()) dp = [] import random pick = [ i for i in range(3,30) ] for _ in range(10): pick_cnt = random.randint(0,20) idx = random.sample(pick, pick_cnt) a = [1,1] for i in range(2,30): if i in idx: a.append(a[-1] + a[-2] - 1) else: a.append(a[-1] + a[-2]) print ( pick_cnt , a[-1] , sum(convert(a[-1])) ) """