본문 바로가기

코드포스

[코드포스 Practice10] B. Mislove Has Lost an Array

Mislove had an array a1, a2, ⋯, an 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 ai either ai=1 or ai is even and there is a number ai2 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 162=8.

According to these facts, he is asking you to count the minimal and the maximal possible sums of all elements in an array.

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

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


 

규칙에 따라 1,2,4,8,16... 2^n-1 까지 숫자는 무조건 있어야 하고 최대냐 최소냐에 따라 특정 수 개수만 달리하면 되겠다 싶었음.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
 
int max_num(int n){
    int tmp = 1;
    for(int i = 0; i < n-1; i++){
        tmp *= 2;
    }
    return tmp;
}
 
int main() {
    int n, l, r;
    scanf("%d %d %d", &n, &l, &r);
    
    int min_sum = 0;
    int tmp = max_num(l);
    for(int i = 0; i < n; i++){
        min_sum += tmp;
        if(tmp != 1)
            tmp /= 2;
    }
    cout << min_sum;
    
    int max_sum = 0;
    int max_t = max_num(r);
    tmp = 1;
    for(int i = 0; i < n; i++){
        max_sum += tmp;
        if(tmp != max_t)
            tmp *= 2;
    }
    cout << " " << max_sum;
    
    
    return 0;
}

 

최소는 먼저 2의 제곱수를 채우고 나머지는 1로 채우면 되고, 최대는 반대로 1부터 2의 제곱수까지 채우고 나머지를 가장 큰 제곱수로 채우면 된다. ㅋㅋ 설명이 구린 건 어쩔 수 없다.. 거 머냐 최소 조건만 만족시키고 나머지는 최솟값이나 최댓값 꽉꽉 채우셈..

 

이렇게 하면 해피 뉴 이어~