[Solution] Anti-knapsack solution codechef

Anti-knapsack solution codechef – You are given two integers NN and KK.

Construct an array AA consisting of NN distinct positive integers such that the following conditions are met:

  • 1Ai2104;1≤Ai≤2⋅104;
  • There exists no subsequence of AA with sum KK.

It can be shown that the answer always exists.

[Solution] Anti-knapsack solution codechef

  • The first line contains a single integer TT: the number of test cases.
  • The only line of each test case contains two integers NN and KK – as mentioned in the statement.

Output Format

For each test case, print a single line containing NN space-separated elements: A1,A2,,ANA1,A2,…,AN. If there are multiple answers, you may print any.

Constraints

  • 1T201≤T≤20
  • 1N10001≤N≤1000
  • 1K1061≤K≤106

[Solution] Anti-knapsack solution codechef

 

2
4 10
10 1000000

Sample Output 1 

1 2 5 6
327 8695 4 19852 14 736 46 15 37 928

[Solution] Anti-knapsack solution codechef Explanation

Test case 11: A=[1,2,5,6]A=[1,2,5,6]. All elements of the array are distinct. Also, 1Ai21041≤Ai≤2⋅104, and there isn’t any subsequence of the array with sum 1010.

Some other valid answers are: [2,6,5,1][2,6,5,1] and [3,27,869,541][3,27,869,541].

Test case 22: A=[327,8695,4,19852,14,736,46,15,37,928]A=[327,8695,4,19852,14,736,46,15,37,928]. All elements of the array are distinct. Also, 1Ai21041≤Ai≤2⋅104, and there isn’t any subsequence of the array with sum 10000001000000.

For Solution

Click here

Leave a Comment