| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 (추가 시간 없음) | 1024 MB | 39 | 21 | 20 | 60.606% |
Alan and Barbara suddenly felt like playing with numbers. Alan chooses a non-empty subset from the set of first $N$ positive integers (1,2,ドル\dots ,N$). Barbara takes the rest of the numbers (if any) from the set. And then they both calculate the sum of the elements in their respective sets.
Alan believes in a magic ratio, which is $X:Y$. Hence, Alan wants to choose the subset in such a way that the ratio between the sum of Alan's subset and the sum of Barbara's subset is exactly $X:Y$.
Can you help Alan to choose a subset that can achieve the desired ratio?
The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
Each test case has a single line containing three integers, $N,ドル $X$ and $Y,ドル as described above.
For each test case, output the first line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is POSSIBLE, if Alan can choose such a non-empty subset, and IMPOSSIBLE otherwise.
If you print POSSIBLE, then output two more lines for that test case.
In the second line, print a single integer, which denotes the size of Alan's subset.
In the third line, print the integers present in Alan's subset.
If there are multiple solutions, you can print any of them.
3 3 1 2 3 1 1 3 1 3
Case #1: POSSIBLE 1 2 Case #2: POSSIBLE 2 1 2 Case #3: IMPOSSIBLE
In the first test case, Alan chooses $\{2\}$. Then Barbara gets $\{1,3\},ドル which sums up to 1ドル+3=4$. So the ratio is 2ドル:4,ドル which is equivalent to 1ドル:2$.
In the second test case, Alan chooses $\{1,2\},ドル which sums up to 1ドル+2=3$. And Barbara gets $\{3\}$. So the ratio is 3ドル:3,ドル which is equivalent to 1ドル:1$.
In the third test case, it is not possible for Alan to choose a subset that satisfies the condition.
Contest > Google > Kick Start > Google Kick Start 2022 > Round C B번