## Fibonacci Presents

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Santa was very busy traveling around the world handing out presents. So busy, in fact, that he forgot to give you one! Not offended in the least, (it's just a Christmas present) you decide to break into Santa's place and claim what is rightfully yours.

Arriving at Santa's house, you realize that his bag can store items with a total mass equal to the Fibonacci number. Any amount more or less would result in very un-Christmas-y consequences. Looking around, you notice a heap of presents. The present has a mass equal to the (1-based) Fibonacci number, and a coolness factor of . Deciding that Santa needs a quick reminder to bring you a present next year, you decide to maximize the coolness of the presents you "liberate".

#### Input Specification

Line : Two space separated integers and , the mass capability of Santa's sack and the number of presents, respectively.
Lines : an integer , the present's coolness.

#### Output Specification

A single integer, the maximal coolness of stolen items. If this is not possible, output -1 instead.

#### Sample Input

12 11
0
0
1
4
7
2
8
10
8
12
10

#### Sample Output

37

#### Explanation for Sample Output

The presents have masses of , , , , , , , , , and , while the required mass is . Take the presents with mass of , , , and , for a total coolness of .

• commented on Aug. 1, 2017, 9:15 p.m. edit 3

What a meme

• commented on July 25, 2017, 11:02 p.m. edited

What's wrong with my code?

I've reviewed and revised it quite a few times but I can't AC anything except the edge cases. It runs the sample correctly along with other test cases I made up. Is it a problem with my method or is it something else?

Any tips?

• commented on Feb. 17, 2017, 10:08 a.m.

lol 1

• commented on Jan. 1, 2017, 6:13 p.m.

Any tips for why case #13 would cause an issue?

• commented on Jan. 1, 2017, 6:15 p.m.

All I can say is that all the test cases have been verified and they are correct, including test case 13.

• commented on Jan. 1, 2017, 6:23 p.m.

Im not saying its wrong im just hoping for a pointer

• commented on Jan. 1, 2017, 6:26 p.m.

We'll tell you after the contest is over!

• commented on Jan. 2, 2017, 1:58 a.m.

Is the contest over, can we discuss?

• commented on Jan. 2, 2017, 2:14 a.m.

Yes, you may. Editorials will be released tomorrow.

Btw, test case 13 was an edge case when k=1 and n>=2.

• commented on Jan. 2, 2017, 4:08 a.m.

OK, Thank you.

• commented on Jan. 1, 2017, 6:10 p.m. edited

nvm233

• commented on Jan. 1, 2017, 1:40 p.m.

Is the sample input correct? why can't we just take all except 89 weight for coolness of 52?

• commented on Jan. 1, 2017, 1:42 p.m. edited