P1021 [NOIP 1999 Senior] Stamp Denomination Design (suspected wrong problem)

除直接打表外，本题不保证存在**正确且时间复杂度可以通过全部数据**做法。由于测试数据过水，部分错误做法可以通过此题，通过不代表做法正确。本题不接受 hack 数据。 [关于此类题目的详细内容。](https://www.luogu.com.cn/paste/pf94n89x)

Given an envelope on which at most $N$ stamps may be affixed, determine, for given $K$ types of stamps (with $N+K \le 15$ and assuming an unlimited supply of each type), how to design the stamp denominations to obtain the largest value $\mathsf{MAX}$ such that every postage value from $1$ to $\mathsf{MAX}$ can be formed. For example, when $N=3$, $K=2$: if the denominations are $1$ fen and $4$ fen, then every postage value between $1\sim 6$ can be formed (and, of course, also $8$, $9$, and $12$); if the denominations are $1$ fen and $3$ fen, then every postage value between $1\sim 7$ can be formed. One can verify that when $N=3$ and $K=2$, $7$ is the largest consecutive postage value that can be obtained, so $\mathsf{MAX}=7$, with denominations $1$ fen and $3$ fen.

Two integers, representing $N$ and $K$.

Output a total of $2$ lines. On the first line, output the chosen denominations in ascending order. On the second line, output `MAX=S`, where $S$ denotes the maximum consecutive postage value.

Translated by ChatGPT 5