BTCK - A problem of Backtracking
You have to solve the following problem with backtracking. You're given a sequence of 10 positive integers n1, n2, n3 ... n9, n10 and a positive value K.
To solve this problem you need to print a permutation a1, a2, a3 ... a10 of the numbers {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} such that a1 * n1 + a2 * n2 + a3 * n3 + ... + a10 * n10 ≤ K.
Input
In the first line, a single integer T, the number of test cases.
For each test case there will be two lines:
In the first line, 10 positive integers (1 ≤ n_i ≤ 10^9) separated by spaces.
In the second line, a single positive integer K (1 ≤ K ≤ 10^9).
Output
For each test case, print a line with the answer for that test case as following:
Among all the permutations that solve the problem according to the description above, print the lexicographically smallest.
You've to print the permutation in a single line, separating each integer by a simple space.
If no such permutation exists, print a single line with "-1".
Example
Input: 2 1 2 3 4 5 6 7 8 9 10 200 1 2 3 4 5 6 7 8 9 10 100 Output: 2 6 8 9 7 5 4 3 1 0 -1
hide comments
bsubercaseaux:
2024-09-03 02:12:56
Problem creator here: sorry about the issue in the original problem statement; I wasn't careful back in 2016. I have corrected it now. |
|
Lars Krapf:
2023-02-24 22:16:01
WARNING: As dawid_zwiewka already mentioned below, the problem description is *wrong*. You have to print the lexicographically smallest permutation that is *less or equal* than k. |
|
manav0299:
2021-03-05 21:29:59
Normal Backtracking, just use pruning Last edit: 2021-03-07 20:56:43 |
|
krishnanshu:
2020-04-13 14:44:14
this question is similar N queen.
|
|
pabloskimg:
2019-02-07 16:42:06
Make sure to include pruning to avoid TLE Last edit: 2019-02-07 16:42:58 |
|
rockintosh:
2019-01-24 16:00:50
Can anyone tell me if bfs based approach could help here? |
|
sonianand966:
2018-10-13 21:23:21
I tried studying recursion and backtracking but it never works for me.
|
|
learnerinblack:
2018-06-10 19:18:01
Nothing to do with backtracking. In fact backtracking gives TLE. Last edit: 2018-06-10 21:08:39 |
|
recurze:
2018-01-04 17:01:23
@ztoa1: I finally got what you meant! thank you :)
|
|
Arkadiusz Bulski:
2017-12-28 22:55:54
The formula seems to have buggy "+" placement, its a simple sum linear combination, right? Last edit: 2017-12-28 22:56:11 |
Added by: | BerSub |
Date: | 2016-10-04 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |