Description

It’s Wildcat’s birthday, and of course everyone is bringing gifts (ahem, those who didn’t, take note!). Not knowing what to buy and considering practicality, everyone decides to chip in to buy Wildcat a birthday cake. They don’t know the exact price of the cake, but they can set a price estimate, i.e., they will buy a cake that does not exceed a certain amount. The OIers then pose a challenge: can we use the fewest number of coins to make all values within the estimate range, so that no matter the cake’s price, no change is needed?

This leads to the following problem: for a given $n$, can we use the fewest distinct positive integers to form all positive integers up to and including $n$? If yes, what is the minimal number of positive integers required, and with that minimal number, how many different ways are there?

Input Format

A single line containing an integer $n\ (1\le n\le 1000)$.

Output Format

One line with two numbers: the first is the minimal required count, and the second is the number of compositions using that minimal count. The two answers are separated by a space.

6

3 2

Hint

Using three numbers is minimal; there are two methods: $1,2,3$ and $1,2,4$.

• For $1,2,3$ there are $1,2,3$，$1+3$，$2+3$，$1+2+3$.
• For $1,2,4$ there are $1$，$2$，$1+2$，$4$，$1+4$，$2+4$.

Translated by ChatGPT 5