4461. Range Partition (Google Kickstart2022 Round C Problem B)

1：题目

Ellen and Barbara play a numbers game together.

给定前 N 个正整数 1∼N.

首先,It's up to Allen to pick some numbers out of them（不能不取）,然后,Barbara selects all the remaining numbers（如果有的话）.

Let the sum of all the numbers Allen pick be A,The sum of all numbers chosen by Barbara is B.

现在,given a ratio X:Y,要求 A:B 恰好等于 X:Y.

Could you please give a reasonable scheme for Allen to choose the numbers.

输入格式
第一行包含整数 T,表示共有 T 组测试数据.

每组数据占一行,包含三个整数 N,X,Y.

输出格式
Each set of data first outputs a row of results,形如 Case #x: y,其中 x 为组别编号（从 1 开始）,y 为 POSSIBLE（A reasonable solution exists）,或 IMPOSSIBLE（There is no reasonable solution）.

如果A reasonable solution exists,Then there are two more lines of results to output,第一行输出一个整数,Represents the number of digits that Allen picks,The second line outputs the numbers selected by Allen.

如果答案不唯一,则输出任意合理方案均可.

数据范围
1≤T≤100,
1≤X,Y≤108,
gcd(X,Y)=1,
1≤N≤5000.

输入样例：
3
3 1 2
3 1 1
3 1 3
输出样例：
Case #1: POSSIBLE
1
2
Case #2: POSSIBLE
2
1 2
Case #3: IMPOSSIBLE
样例解释
对于 Case 1,Ellen chose 2,Barbara chose 1,3,因此 A=2,B=1+3=4,比率为 2:4,The ratio with the given ratio 1:2 相等.

对于 Case 2,Ellen chose 1,2,Barbara chose 3,因此 A=1+2=3,B=3,比率为 3:3,The ratio with the given ratio 1:1 相等.

对于 Case 3,There is no rational choice of numbers.
难度：简单
时/空限制：1s / 64MB
总通过数：387
总尝试数：881
来源：Google Kickstart2022 Round C Problem B
算法标签
None

2：代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 5010;
int n, x, y;
int ans[N];

int main()
{
    
    int T;
    cin >> T;
    for (int t = 1; t <= T; t ++)
    {
    
        cin >> n >> x >> y;
        int sum = 0;
        for (int i = 1; i <= n; i ++) sum += i;

        int b = sum / (x + y);

        if (sum % (x + y)) printf("Case #%d: IMPOSSIBLE\n", t);
        else 
        {
    
            memset(ans, 0, sizeof ans);
            printf("Case #%d: POSSIBLE\n", t);
            int cnt = 0;
            int s = x * b;
            for (int i = n; i >= 1; i --)
            {
    
                if (s >= i) 
                {
    
                    s -= i;
                    ans[cnt ++] = i;
                }
            }
            cout << cnt << endl;
            for (int i = 0; i < cnt; i ++)
                cout << ans[i] << ' ';
            cout << endl;
        }
    }
}