問題一覧 > 通常問題

No.2167 Fibonacci Knapsack

レベル : / AI推定難易度 : 2350 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 24
作問者 : chineristAC / テスター : 👑 hamamu
お気に入りにしたユーザー ProblemId : 8871 / 自分の提出
問題文最終更新日: 2022-12-18 21:48:23
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2022 (順位表) の他の問題:

Problem Statement

Let the Fibonacci numbers $F_n$ be the sequence defined by the following recurrence. $$F_n = \begin{cases} 1 & n = 1 \\ 2 & n = 2 \\ F_{n - 2} + F_{n - 1} & n \ge 3 \end{cases}$$

There are $N$ items, numbered $1, 2, \ldots, N$. For each $i = 1, 2, \ldots, N$, item $i$ has weight $w_i$ and value $F_{i}$.

Magurofly is going to pack some of these items into a suitcase and carry them. However, the total weight packed into the suitcase must be at most $W$.

Find the maximum possible total value of the items packed into the suitcase (if there is no item that can be packed into the suitcase, the answer is $0$). It can be proved that, under the constraints of this problem, the total value does not exceed $10^{18}$.

Solve this for $T$ test cases.

Input

The input is given in the following format.
$T$
$case_1$
$case_2$
$\vdots$
$case_{T}$
Each test case is given in the following format.
$N$ $W$
$w_1$ $w_2$ $\dots$ $w_N$
  • $1 \le T \le 100$
  • $1 \le N \le 75$
  • $1 \le W \le 10^{18}$
  • $1 \le w_i \le 10^{16}$
  • All input values are integers.

Output

Output $T$ lines. On the $i$-th line, output the answer to the $i$-th test case.

Sample

Sample 1
Input
1
5 7
1 2 3 4 5
Output
10

Choosing items $2,\ 5$ makes the total value $F_2+F_5=2+8=10$. There is no way to make the total value any larger, so the answer is $10$.

Sample 2
Input
1
5 7
8 9 10 11 12
Output
0

The weight of an item may exceed $W$. In this case, not even $1$ item can be packed into the suitcase, so the answer is $0$.

Sample 3
Input
2
11 50
1 3 3 3 12 129 13 34 68 30 24
20 6023
286 1304 1882 1144 6 1154 642 136 1076 1638 968 1266 448 374 288 1298 1708 1344 580 1088
Output
176
26492

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。