Codeforces Round #774 (Div2) - C. Factorials and Powers of Two

문제

A number is called powerful if it is a power of two or a factorial. In other words, the number m is powerful if there exists a non-negative integer𝑑d such that m=2^d or m=d!, whered!=1⋅2⋅…⋅d (in particular, 0!=10!=1). For example 1, 4, and 6 are powerful numbers, because 1=1!, 4=2^2, and 6=3! but 7, 10, or 18 are not.

You are given a positive integer n. Find the minimum number k such that n can be represented as the sum of k distinct powerful numbers, or say that there is no such k.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). Description of the test cases follows.

A test case consists of only one line, containing one integer n (1≤n≤10^12).

Output

For each test case print the answer on a separate line.

If n can not be represented as the sum of distinct powerful numbers, print −1.

Otherwise, print a single positive integer  — the minimum possible value of k.

---

풀이

정해진 수가 주어지면 그 수를 2의 제곱수나 factorial의 합으로 나타낼 수 있는지 확인하는 문제이다. (중복된 수로 이뤄지면 안 된다.)

 

10^9까지 모든 2의 제곱수와 factorial 수를 구하여 벡터에 넣고 오름차순 정렬을 한 다음 만약 n보다 작은 수가 나올 경우 그 수를 무조건 합에 포함시키는 방식으로 하였는데 예외가 있어서 그런지 틀렸다.

 

브루트 포스 방식으로 n보다 작은 수가 나올 경우 재귀를 돌고, 여태까지 합에 포함된 수의 개수가 ans보다 같거나 큰 경우, 현재 인덱스까지  벡터의 누적 합이 n보다 작은 경우는 제외시켜 경우의 수를 줄였더니 통과하였다.

 

1. 10^9 이하의 2의 제곱수와 factorial 수를 벡터 v에 중복 없이 넣고 오름차순 정렬을 한다.
2. v의 누적 합을 prefix_sum 벡터에 저장한다.
3. 합에 포함된 수가 ans보다 같거나 큰 경우, 현재 인데스까지의 누적합이 n보다 작은 경우를 제외하고, n이 v[idx]보다 작을 경우    재귀를 돌면서 모든 경우의 수를 본다. 

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

ll MAX=1000000000000;
vector<ll> v;
map<ll,int> Map;
vector<ll> prefix_sum;

int ans;

void cal(int idx,ll n,int cnt){
    //현재까지 합에 포함된 수가 답과 같거나 크면 return
    if(cnt>=ans) return;
    if(n==0){
        ans=min(ans,cnt);
        return;
    }
    if(idx<0) return;
    
    // n이 누적 합보다 크면 의미가 없으므로 return
    if(n>prefix_sum[idx]) return;

    if(n>=v[idx]){
        cal(idx-1,n-v[idx],cnt+1);
        cal(idx-1,n,cnt);
    }else cal(idx-1,n,cnt);
    
    
}

// factorial을 넣어주는 함수
void factorial(ll fac,ll n){
    if(fac>MAX) return;
    //Map을 이용해 중복을 방지한다.
    if(Map[fac]==0){
        Map[fac]++;
        v.push_back(fac);
    }
    factorial(fac*(n+1),n+1);
}

//2의 제곱수를 넣어주는 함수
void power_two(ll po){
    if(po>MAX) return;
    //Map을 이용해 중복을 방지한다.
    if(Map[po]==0){
        Map[po]++;
        v.push_back(po);
    }
    power_two(po*2);
}

void input() {
}

void init() {
    factorial(1,1);
    power_two(1);
    // 벡터를 오름차순 정리
    sort(v.begin(),v.end());
    
    prefix_sum.resize(v.size());
    
    //누적 합을 구한다.
    prefix_sum[0]=v[0];
    for(int i=1;i<v.size();i++)
        prefix_sum[i]=v[i]+prefix_sum[i-1];
    
}


void solution() {
    ans=INT_MAX;
    ll n; cin>>n;
    cal(v.size()-1,n,0);
    if(ans==INT_MAX) cout<<-1<<endl;
    else cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    init();
    int T; cin>>T;
    while(T--){
        solution();
    }
    return 0;
}