题目描述

在霍格沃茨魔法学院，学生们面临着一个独特的挑战：他们需要使用最少的不同魔法币面额来凑成从1到 n 以内的所有正整数。这是一个魔法世界中的货币兑换问题，学生们必须找到一种方法，使得无论他们需要支付多少魔法币，都能直接支付，而不需要找零。 挑战任务： 1.确定是否能够使用最少的不同正整数（魔法币面额）来组成从1到 n 以内的所有正整数。 2.如果可以，找出最少需要多少个不同的正整数（魔法币面额）。 3.计算出使用最少个数的魔法币面额有多少种不同的组成方法。 魔法数学挑战： 现在，让我们来挑战一下具体的数字。假设 n=15，我们需要找出最少的不同正整数（魔法币面额）来组成从1到15的所有正整数。 解答： 1.能否组成： 是的。 2.最少需要的正整数：4 个不同的魔法币面额。 3.不同的组成方法： 我们可以选择面额为 1, 2, 4, 8 的魔法币。这样，我们可以通过组合这些面额来组成1到15的任何数。 组成方法示例：

1 = 1，2 = 2，3 = 1 + 2，4 = 4，5 = 4 + 1，...15 = 8 + 4 + 2 + 1

这个问题在魔法世界中是一个有趣的数学挑战，学生们可以通过解决这个问题来锻炼他们的魔法数学技能。

Input Format

只有一行包含一个整数n (1≤n≤1000)。

Output Format

一行两个数，第一个数是最少需要多少个数，第二个数是用最少个数的组成方案个数。两个答案用空格分隔。

输入数据 1

6

输出数据 1

3 2

Hint

最少用三个数，有两种方法，分别是： 1,2,3 和 1,2,4。 对于 1,2,3 有 1,2,3，1+3，2+3，1+2+3；

对于 1,2,4 有 1，2，1+2，4，1+4，2+4。

Source

比赛题