范围分区（暑假每日一题 39）

艾伦和芭芭拉一起玩数字游戏。

给定前 $N$ 个正整数 $1\sim N$。

首先，由艾伦从中选取一些数字（不能不取），然后，芭芭拉选取剩余所有数字（如果有的话）。

不妨设艾伦选取的所有数字之和为 $A$，芭芭拉选取的所有数字之和为 $B$。

现在，给定一个比率 $X:Y$，要求 $A:B$ 恰好等于 $X:Y$。

请你给出一种艾伦选取数字的合理方案。

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

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

输出格式
每组数据首先输出一行结果，形如 Case #x: y，其中 $x$ 为组别编号（从 $1$ 开始），$y$ 为 POSSIBLE（存在合理方案），或 IMPOSSIBLE（不存在合理方案）。

如果存在合理方案，则还需输出两行结果，第一行输出一个整数，表示艾伦选取的数字数量，第二行输出艾伦选取的数字。

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

数据范围
$1\le T\le 100,$
$1\le X,Y\le 108,$
$gcd(X,Y)=1,$
$1\le N\le 5000$。

输入样例：

3
3 1 2
3 1 1
3 1 3
1
2
3
4

输出样例：

Case #1: POSSIBLE
1
2
Case #2: POSSIBLE
2
1 2
Case #3: IMPOSSIBLE
1
2
3
4
5
6
7

样例解释
对于 Case 1，艾伦选择了 $2$，芭芭拉选择了 $1,3$，因此 $A=2,B=1+3=4$，比率为 $2:4$，该比率与给定比率 $1:2$ 相等。

对于 Case 2，艾伦选择了 $1,2$，芭芭拉选择了 $3$，因此 $A=1+2=3,B=3$，比率为 $3:3$，该比率与给定比率 $1:1$ 相等。

对于 Case 3，不存在合理选取数字方案。

---

#include
#include

using namespace std;

int t;
int n, x, y;

int main(){
    
    scanf("%d", &t);
    for(int l = 1; l <= t; l++){
        
        scanf("%d%d%d", &n, &x, &y);
        printf("Case #%d: ", l);
        
        int sum = n * (n + 1) / 2;
        if(sum % (x + y)) puts("IMPOSSIBLE");
        else{
            
            puts("POSSIBLE");
            int a = sum / (x + y) * x;
            vector<int> q;
            for(int i = n; i >= 1; i--)
                if(a >= i){
                    q.push_back(i);
                    a -= i;
                }
            printf("%d\n", q.size());
            for(int i = q.size() - 1; i >= 0; i--)
                printf("%d ", q[i]);
            puts("");
        }
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37