問題一覧 > 通常問題

No.1782 ManyCoins

レベル : / AI推定難易度 : 1875 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 36
作問者 : ei1333333 / テスター : Luzhiled
お気に入りにしたユーザー ProblemId : 7367 / 自分の提出
問題文最終更新日: 2021-12-08 17:45:00
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 2021 (順位表) の他の問題:

Problem Statement

There are $N$ types of coins, coin $1$ through coin $N$, and there are $10^{100000}$ coins of each type. The value per $1$ coin of coin $i\ (1 \leq i \leq N)$ is $W_i$.

Among the values from $1$ to $L$ inclusive, find how many distinct values can be made by choosing $1$ or more coins. You may choose multiple coins of the same type.

Formally, find the number of integers $k$ that satisfy all of the following conditions.

  • $1 \leq k \leq L$
  • There exists a sequence $c$ of non-negative integers of length $N$ such that $\displaystyle \sum_{i=1}^{N} c_i W_i = k$

Input

$N$ $L$
$W_1$ $W_2$ $\cdots$ $W_N$
  • $1 \leq N \leq 20$
  • $1 \leq L \leq 10^{12}$
  • $1 \leq W_i \leq 10^6$
  • If $i \neq j$, then $W_i \ne W_j$
  • All inputs are integers

Output

Print the answer on $1$ line.

Sample

Sample 1
Input
2 10
5 2
Output
8

There exist ways of choosing coins whose total value is $2, 4, 5, 6, 7, 8, 9, 10$.

Sample 2
Input
5 30014
10001 10002 10003 10004 10005
Output
26
Sample 3
Input
3 1000000000000
1 2 3
Output
1000000000000

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