Skip to content

Latest commit

 

History

History
62 lines (32 loc) · 1.1 KB

File metadata and controls

62 lines (32 loc) · 1.1 KB

POI 2011/2012 XIX

Stage I

[Festyn (fes)]

[Litery (lit)]

[Studnia (stu)]

[Randka (ran)]

[Odległość (odl)]

Stage II

Day 0

[Tour de Bajtocja (tou)]

Day 1

[Bony (bon)]

[Szatnia (sza)]

Day 2

[Okropny wiersz (okr)]

Rozkład Fibonacciego (roz)

题意:给出一个整数$N$,可以用斐波那契数加加减减得到,求出最小需要的项数。

$1 \le N \le 4 \times 10^{17}$

题解:令$f(n)$表示最小需要的项数,$a$是小于等于$n$的最大斐波那契数,$b$是大于等于$n$的最小斐波那契数。那么显然有$f(n)=\min(f(n-a),f(b-n))+1$,记忆化一下就好了。

Final Stage

Day 0

[Squarki (squ)]

Day 1

[Licytacja (lic)]

[Pensje (pen)]

[Wyrównywanie terenu (wyr)]

Day 2

[Bezpieczeństwo minimalistyczne (bez)]

[Hurtownia (hur)]

[Prefiksufiks (pre)]