NOIP '99 P4 - Stamp Face Value Design - DMOJ: Modern Online Judge

NOIP '99 P4 - Stamp Face Value Design

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 64M

Problem type

Given an envelope, at most $N$ ~N~ stamps are allowed to be pasted. Calculate how to design the face value of stamps so for the maximum value $MAX$ ~MAX~ where every postage between $1$ ~1~ and $MAX$ ~MAX~ can be obtained if given $K$ ~K~ ( $N+K \le 13$ ~N+K \le 13~) types of stamps (assuming there are infinitely many stamps of each type).

For example, $N = 3$ ~N = 3~, $K = 2$ ~K = 2~, if the face values are $1$ ~1~ cent and $4$ ~4~ cents, then every postage between $1 \sim 6$ ~1 \sim 6~ cents will be able to be obtained. Every postage between $1 \sim 7$ ~1 \sim 7~ cents can be obtained if the face values are $1$ ~1~ cent, and $3$ ~3~ cents, respectively. It can be proven that when $N = 3$ ~N = 3~, $K = 2$ ~K = 2~, $7$ ~7~ cents is the maximum continuous postage that can be obtained, so $MAX = 7$ ~MAX = 7~ and the face values are $1$ ~1~ cent and $3$ ~3~ cents respectively.

Input Specification

The input contains two integers, $N$ ~N~ and $K$ ~K~.

Output Specification

There should be two lines of output.

The first line of output should contain the face values chosen to maximize $MAX$ ~MAX~ in increasing order.

Output MAX=S on the second line, where $S$ ~S~ represents the maximum postage that can be obtained.

Sample Input

3 2

Sample Output

1 3
MAX=7

Problem translated to English by Tommy_Shan.

Comments

0

leiterally commented on June 2, 2025, 4:51 p.m.

On Luogu it says: "Unless you output the answer using a chart of all possible combinations and their corresponding answers, there is no guaranteed solution to this problem. The test data was too weak for this problem, and many incorrect solutions can pass the problem. AC does not mean your solution is correct. No hack data is accepted for this problem."