第一讲. 열거형

1.ABC 추측

열거형 A와 B를 통해 C의 범위를 B부터 N/A/B로 설정합니다. B ≤ N/A/B일 때, C의 개수는 N/A/B - B입니다. A의 열거형 범위는 A³ ≤ N이며, B의 열거형 범위는 A*B² ≤ N입니다.

코드 보기

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

int n;
ll ans;

int main(){
    cin >> n;
    for(ll a = 1; a*a*a <= n; ++a){
        for(ll b = a; a*b*b <= n; ++b){
            ll c = n / (a * b);
            if(c >= b)
                ans += c - b + 1;
            else break;
        }
    }
    cout << ans;
    return 0;
}

2. 등差点수

답안의 자리수는 입력값 X의 자리수와 같아야 합니다. k자리수의 최대 등差点수는 k개의 9입니다. 입력값 X와 같은 자리수를 가지는 9개의 수는 항상 X보다 크거나 같습니다. 등差点수를 생성하기 위해 최초항목(d)와 차이(d)를 열거합니다. 생성된 등差点수가 X보다 크면 accept합니다.

코드 보기

#include<bits/stdc++.h>

using namespace std;

int main(){
    string x;
    cin >> x;
    int n = x.size();
    int a[n+1];
    for(int i = 0; i < n; ++i)
        a[i+1] = x[i] - '0';
    
    for(int d = 1; d <= 9; ++d){
        for(int t = -9; t <= 9; ++t){
            int b = d;
            bool valid = true;
            bool larger = false;
            for(int i = 1; i <= n; ++i){
                if(b > 9 || b < 0){
                    valid = false;
                    break;
                }
                if(!larger){
                    if(b > a[i])
                        larger = true;
                    else if(b < a[i]){
                        valid = false;
                        break;
                    }
                }
                b += t;
            }
            if(valid){
                b = d;
                for(int i = 1; i <= n; ++i){
                    cout << b << (b += t);
                }
                return 0;
            }
        }
    }
    return 0;
}

3. M ≤ ab

n² ≤ m일 때는 불가능합니다. n ≥ m일 때는 답이 m입니다. 다른 경우에는 a를 열거하고 b = ⌈m/a⌉로 설정합니다. b가 n보다 작으면 a*b를 최소화합니다.

코드 보기

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

int main(){
    ll n, m;
    cin >> n >> m;
    if(n < m / n || (m % n != 0 && n == m / n)){
        cout << -1;
        return 0;
    }
    if(n >= m){
        cout << m;
        return 0;
    }
    
    ll limit = sqrt(m) + 3;
    ll ans = LLONG_MAX;
    for(ll a = 1; a <= limit && a <= n; ++a){
        ll b = (m + a - 1) / a;
        if(b > n) continue;
        ans = min(ans, a * b);
    }
    cout << ans;
    return 0;
}

4. 캔开启

물건을 3개의 분류로 나눕니다. 각 분류를 내림차순으로 정렬하고, 가장 큰 값을 선택합니다. 선택한 개수를 통해 필요한开启기 수를 결정합니다.

코드 보기

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

int main(){
    ll n, m;
    vector<ll> v[3];
    ll ans;
    ll qzh[200005];
    
    sort(v[0].begin(), v[0].end(), greater<ll>());
    sort(v[1].begin(), v[1].end(), greater<ll>());
    sort(v[2].begin(), v[2].end(), greater<ll>());
    
    for(int i = 1; i <= v[0].size(); ++i)
        qzh[i] = qzh[i-1] + v[0][i-1];
    
    int j = 0, gs = 0;
    int da = 0;
    ans = qzh[min((int)v[0].size(), m)];
    for(int i = 0; i < v[1].size(); ++i){
        ll x = v[1][i];
        if(gs < i+1){
            if(j+1 <= v[2].size()){
                j++;
                gs += v[2][j-1];
            }
            else break;
        }
        da += x;
        if(i+1 + j > m) break;
        ans = max(ans, da + qzh[min((int)v[0].size(), m - i - 1 - j)]);
    }
    cout << ans;
    return 0;
}