[Solution] Range Partition Solution Round C 2022 - Kick Start 2022

[Solution] Range Partition Solution Round C 2022 - Kick Start 2022

Problem

Alan and Barbara suddenly felt like playing with numbers. Alan chooses a non-empty subset from the set of first N$N$ positive integers (1,2,…,N$1,2,\dots ,\mathbf{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$\mathbf{X}:\mathbf{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$\mathbf{X}:\mathbf{Y}$.

Can you help Alan to choose a subset that can achieve the desired ratio?

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.

Solution Click Below:-  CLICK HERE

Each test case has a single line containing three integers, N$N$, X$X$ and Y$Y$, as described above.

Output

For each test case, output the first line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is POSSIBLE, if Alan can choose such a non-empty subset, and IMPOSSIBLE otherwise.

New Password Solution Round C 2022

Range Partition Solution Round C 2022

Ants on a Stick Solution Round C 2022

Palindromic Deletions Solution Round C 2022

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.

Limits

Time limit: 5 seconds.
Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤X≤108$1\le \mathbf{X}\le {10}^8$.
1≤Y≤108$1\le \mathbf{Y}\le {10}^8$.
gcd(X,Y)=1$gcd(\mathbf{X},\mathbf{Y})=1$, where gcd is Greatest common divisor.

Test Set 1

1≤N≤15$1\le \mathbf{N}\le 15$.

Test Set 2

1≤N≤5000$1\le \mathbf{N}\le 5000$.