No sequence Codechef solutions Today | Codechef Starters 72 ✅ (100/100) FULL | AC Code ✅| NOSEQ

Problem

Alice gave Bob $3$ integers $N, K,$ and $S$. Help Bob find an $S$-good sequence.

A sequence $B$ of length $N$ is called $S$-good if the following conditions are met:

• $B_i \in \{-1, 0, 1\}$ for each $1 \leq i \leq N$
• $\sum_{i=1}^N B_i\cdot K^{i-1} = S$

If there are multiple $S$-good sequences, print any of them.
If no $S$-good sequence exists, print $-2$.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of a single line of input containing three space-separated integers — $N, K,$ and $S$.

Output Format

For each test case:

• If no $S$-good sequence exists, print $-2$.
• Otherwise, output $N$ space-separated integers denoting the $S$-good sequence.

If multiple $S$-good sequences exist, you may print any of them.

Constraints

Sample 1:

3
4 2 15
3 6 36
5 5 7

1 1 1 1
0 0 1
-2

Explanation:

Test case $1$: We have $B = [1,1,1,1]$ and $S = 15$
$\sum_{i=1}^N B_i\cdot K^{i-1} = 1\cdot 1 + 2\cdot 1 + 4\cdot 1 + 8\cdot 1 = 15$, hence $B$ is an $S$-good sequence.

Test case $2$: We have $B = [0, 0, 1]$ and $S = 36$. $6^2 = 36$ so clearly $B$ is $S$-good.

Test case $3$: No $S$-good sequence of length $5$ exists.