hotpepsiの練習帳

SRM 687

22:49

https://competitiveprogramming.info/topcoder/srm/round/16708/div/1

Div1 Easy (250) AlmostFibonacciKnapsack

問題

• フィボナッチ数列っぽい数列が与えられる
• A[1] = 2
• A[2] = 3
• A[n] = A[n-1] + A[n-2] - 1
• 数Xが与えられたとき、この数列の異なる要素の和で表せるかどうかを求める

方針

• ???
• (終了後)
• 2以上の任意の数が作れるらしい
• Xから貪欲に引いていけばいいが、残りが1にならないようにする
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_687/AlmostFibonacciKnapsack.cpp

結果

0pt 296th/395 rating 1533 -> 1429 (-104)

全くわからなかった。普通のフィボナッチ数の和でも任意の数を表せるらしい。

http://togetter.com/li/959779