No.1782 ManyCoins
問題文最終更新日: 2021-12-08 17:45:00
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
ei1333333