Positive Prefixes[POSPREFS](Solution)

You are given two positive integers NN and KK, where K≤NK≤N. Find a sequence A1,A2,…,AN such that:

• for each valid ii, AiAi is either ii or −i
• there are exactly KK values of ii such that 1≤i≤N and A1+A2+…+Ai>0

If there are multiple solutions, you may print any one of them. It can be proved that at least one solution always exists.

Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first and only line of each test case contains two space-separated integers NN and KK.

Output

For each test case, print a single line containing NN space-separated integers A1,A2,…,AN.

Constraints

• 1≤T≤1,000
• 1≤K≤N≤1,000

Subtasks

Subtask #1 (10 points): N≤10

Subtask #2 (90 points): original constraints

Example Input

1
3 3

Example Output

1 2 3

SOLUTION

#include<iostream>
using namespace std;
int
main()
{
    int t;
    cin>>t;
    
    while(t--)
    {
        int i,n,k;
        cin>>n>>k;
        
        int arr[n+1],sum = 0,count = 0;
        
        if(n%2 == 0)
        {
            for(i=1; i <= n ;i++)
            {
                if(i%2==0)
                {
                    arr[i] = i;
                    sum = sum + arr[i];
                    if(sum > 0)
                        count++;
                }
                else
                {
                    arr[i] = (-1) * i;
                    sum = sum + arr[i];
                    
                    if(sum > 0)
                        count++;
                }
                // cout<<" " << i<< " . " << arr[i]<<" sum=" << sum << endl;
            }
        }
        else
        {
            for(i=1; i <= n ;i++)
            {
                if(i%2==0)
                {
                    arr[i] = (-1) * i;
                    
                    sum = sum + arr[i];
                    
                    if(sum > 0)
                        count++;
                }
                else
                {
                    arr[i] =  i;
                    sum = sum + arr[i];
                    if(sum > 0)
                        count++;
                }
               // cout<<" " << i<< " . " << arr[i]<<" sum=" << sum << endl;;
            }
        }
       // cout<< " Count = " << count <<endl <<" K = " << k <<endl;
        if( count == k )
        {
            for(i = 1; i <= n; i++)
            {
                cout<< arr[i]<< " ";
            }
        }
        else if( count > k)
        {
            for(i = n   ; i >= 1; i--)
            {
                if(arr[i] > 0)
                     {
                         arr[i] = -1 * arr[i];
                         count--;
                     }
                if(count == k)
                    break;
            }
            
            for(i = 1; i <= n; i++)
            {
                cout<<arr[i]<<" ";
            }
        }
        else if( count < k)
        {
            for(i = n ;i >= 1; i-- )
            {
                if(arr[i] < 0)
                     {
                         arr[i] = -1 * arr[i];
                         count++;
                     }
                if(count == k)
                    break;
            }
            for(i = 1; i <= n; i++)
            {
                cout<<arr[i]<<" ";
            }
            
        }
        
        cout << endl;
    }
    return 0;
}

LINK OF SOLUTION:

Solution: 40135431 | CodeChef

SUPPORT ME ON:

AkjderB

GET IN TOUCH:

AKSHAT KUMAR JAIN