Codeforces Round #705 (Div. 2) A

A. Anti-knapsack

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        float n, k;
        cin >> n >> k;
        vector<int> m;
        for(int i = k+1; i <= n; i++) m.push_back(i);
        for(int i = round(k/2); i < k; i++) m.push_back(i);
        cout << m.size() << "\n";
        for(int i : m) cout << i << " ";
        cout << "\n";
    }
    return 0;
}

원소 합이 k 가 되는 부분집합이 없도록 1부터 n까지 범위에서 숫자들을 선택할 때, 선택할 수 있는 숫자들의 최대 개수를 묻고 있다.

k 보다 큰 값인 원소들은 절대 합이 k 가 될 수 없기 때문에 모두 선택하고, k 보다 작은 수들 중에서는 절반이 최대 고를 수 있는 개수가 된다. 단, k 값이 짝수일 땐 오른쪽에 있는 값들을 선택할 경우 가운데 값을 포함할 수 있다. (반올림 함수를 사용하면 한 번에 처리가 가능하다.)

후기

"합이 k인 선택된 숫자의 부분 집합이 없도록 1부터 n까지 구별되는 최대 정수 수를 선택해야 합니다." 번역을 보고도 이해가 가지 않을 정도로 문제의 설명이 불친절했는지, 파파고의 번역 수준이 낮았는지 는 잘 모르겠다. 영어 지문을 여러 번 읽고 나서야 문제를 이해한 걸 보아, 수준 높은 직독직해의 필요성을 느꼈다.

round 함수를 사용한 걸 보고 hack 을 시도한 것 같다. k 값은 정수이기 때문에 2로 나누어 떨어지지 않을 경우 나머지는 항상 0.5 만큼 남게된다. 따라서 반올림 함수 중 ceil 이 아닌, round 를 사용해도 문제가 없다.