306482: CF1204B. Mislove Has Lost an Array

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Mislove Has Lost an Array

题意翻译

有一个长度为 $n$ 的整数序列 $a_1,\,a_2,\cdots,a_n$ ,满足以下条件 - 序列中不同的数的个数在区间 $[\,l,\,r\,]$ 中 - 序列中的元素只有 $1$ 和偶数,若 $a_i$ 在序列中,那么 $\frac{a_i}{2}$ 也在序列中 对于给定的 $n,\,l,\,r$ 试求出该序列所有元素加和的最大值与最小值 **输入格式** 仅一行,包含三个整数,分别表示 $n,\,l,\,r$ **输出格式** 包含两个整数,分别表示序列所有元素加和的最大值与最小值

题目描述

Mislove had an array $ a_1 $ , $ a_2 $ , $ \cdots $ , $ a_n $ of $ n $ positive integers, but he has lost it. He only remembers the following facts about it: - The number of different numbers in the array is not less than $ l $ and is not greater than $ r $ ; - For each array's element $ a_i $ either $ a_i = 1 $ or $ a_i $ is even and there is a number $ \dfrac{a_i}{2} $ in the array. For example, if $ n=5 $ , $ l=2 $ , $ r=3 $ then an array could be $ [1,2,2,4,4] $ or $ [1,1,1,1,2] $ ; but it couldn't be $ [1,2,2,4,8] $ because this array contains $ 4 $ different numbers; it couldn't be $ [1,2,2,3,3] $ because $ 3 $ is odd and isn't equal to $ 1 $ ; and it couldn't be $ [1,1,2,2,16] $ because there is a number $ 16 $ in the array but there isn't a number $ \frac{16}{2} = 8 $ . According to these facts, he is asking you to count the minimal and the maximal possible sums of all elements in an array.

输入输出格式

输入格式


The only input line contains three integers $ n $ , $ l $ and $ r $ ( $ 1 \leq n \leq 1\,000 $ , $ 1 \leq l \leq r \leq \min(n, 20) $ ) — an array's size, the minimal number and the maximal number of distinct elements in an array.

输出格式


Output two numbers — the minimal and the maximal possible sums of all elements in an array.

输入输出样例

输入样例 #1

4 2 2

输出样例 #1

5 7

输入样例 #2

5 1 5

输出样例 #2

5 31

说明

In the first example, an array could be the one of the following: $ [1,1,1,2] $ , $ [1,1,2,2] $ or $ [1,2,2,2] $ . In the first case the minimal sum is reached and in the last case the maximal sum is reached. In the second example, the minimal sum is reached at the array $ [1,1,1,1,1] $ , and the maximal one is reached at the array $ [1,2,4,8,16] $ .

Input

题意翻译

有一个长度为 $n$ 的整数序列 $a_1,\,a_2,\cdots,a_n$ ,满足以下条件 - 序列中不同的数的个数在区间 $[\,l,\,r\,]$ 中 - 序列中的元素只有 $1$ 和偶数,若 $a_i$ 在序列中,那么 $\frac{a_i}{2}$ 也在序列中 对于给定的 $n,\,l,\,r$ 试求出该序列所有元素加和的最大值与最小值 **输入格式** 仅一行,包含三个整数,分别表示 $n,\,l,\,r$ **输出格式** 包含两个整数,分别表示序列所有元素加和的最大值与最小值

加入题单

上一题 下一题 算法标签: