[Solution] Beautiful Array solution codeforces

Table of Contents

Beautiful Array solution codeforces

Beautiful Array solution codeforces – Stanley defines the beauty of an array 𝑎a of length 𝑛n, which contains non-negative integers, as follows:

𝑖=1𝑛𝑎𝑖𝑘,∑i=1n⌊aik⌋,

which means that we divide each element by 𝑘k, round it down, and sum up the resulting values.

Stanley told Sam the integer 𝑘k and asked him to find an array 𝑎a of 𝑛n non-negative integers, such that the beauty is equal to 𝑏b and the sum of elements is equal to 𝑠s. Help Sam — find any of the arrays satisfying the conditions above.

[Solution] Beautiful Array solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡10001≤t≤1000). Description of the test cases follows.

The first line of each test case contains integers 𝑛n𝑘k𝑏b𝑠s (1𝑛1051≤n≤1051𝑘1091≤k≤1090𝑏1090≤b≤1090𝑠10180≤s≤1018).

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.

Output

For each test case print 1−1 if such array 𝑎a does not exist. Otherwise print 𝑛n non-negative integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖10180≤ai≤1018) — the answer.

[Solution] Beautiful Array solution codeforces

Example
input

Copy
8
1 6 3 100
3 6 3 12
3 6 3 19
5 4 7 38
5 4 7 80
99978 1000000000 100000000 1000000000000000000
1 1 0 0
4 1000000000 1000000000 1000000000000000000
output

Copy
-1
-1
0 0 19
0 3 3 3 29
-1
-1
0
0 0 0 1000000000000000000

[Solution] Beautiful Array solution codeforces

In the first, the second, the fifth and the sixth test cases of the example it is possible to show that such array does not exist.

In the third testcase of the example 𝑎=[0,0,19]a=[0,0,19]. The sum of elements in it is equal to 19, the beauty of it is equal to (06+06+196)=(0+0+3)=3(⌊06⌋+⌊06⌋+⌊196⌋)=(0+0+3)=3.

In the fourth testcase of the example 𝑎=[0,3,3,3,29]a=[0,3,3,3,29]. The sum of elements in it is equal to 3838, the beauty of it is equal to (0+0+0+0+7)=7(0+0+0+0+7)=7.

For Solution

“Click Here”

Leave a Comment