Положительные префиксы[POSPREFS](Решение)

Вам даны два натуральных числа NN и KK, где K≤NK≤N. Найдите последовательность A1,A2,…,AN такую, что:

• для каждого действительного ii AiAi равно либо ii, либо −i
• существует ровно KK значений ii таких, что 1≤i≤N и A1+A2+…+Ai›0

Если решений несколько, можно вывести любое из них. Можно доказать, что всегда существует хотя бы одно решение.

Вход

• Первая строка входных данных содержит одно целое число TT, обозначающее количество тестовых случаев. Ниже приводится описание тестовых случаев TT.
• Первая и единственная строка каждого набора входных данных содержит два целых числа, разделенных пробелом, NN и KK.

Вывод

Для каждого набора входных данных выведите одну строку, содержащую NN целых чисел A1,A2,…,AN, разделенных пробелами.

Ограничения

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

Подзадачи

Подзадача №1 (10 баллов): N≤10

Подзадача 2 (90 баллов): исходные ограничения.

Пример ввода

1
3 3

Пример вывода

1 2 3

РЕШЕНИЕ

#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;
}

ССЫЛКА НА РЕШЕНИЕ:

ПОДДЕРЖИТЕ МЕНЯ:

СВЯЗАТЬСЯ: