Решение задачи Отрезки с нечетной суммой с Codeforces

Без пояснения   Просмотров: 52


Вам задан массив a, состоящий из n целых чисел a1,a2,…,an. Вы хотите разделить его ровно на k непустых непересекающихся подотрезков таким образом, что каждый подотрезок имеет нечетную сумму (то есть для каждого подотрезка должно выполняться, что сумма элементов, принадлежащих этому подотрезку, нечетна). Переставлять элементы заданного массива нельзя. Каждый из n элементов массива a должен принадлежать ровно одному из k подотрезков.

Рассмотрим некоторые примеры разделения массива длины 5 на 3 подотрезка (необязательно с нечетной суммой): [1,2,3,4,5] — это изначальный массив, тогда все возможные способы разделить его на 3 непустых непересекающихся подотрезка описаны ниже:

[1],[2],[3,4,5];
[1],[2,3],[4,5];
[1],[2,3,4],[5];
[1,2],[3],[4,5];
[1,2],[3,4],[5];
[1,2,3],[4],[5].
Конечно же, существуют случаи, когда невозможно разделить изначальный массив ровно на k подотрезков таким образом, что сумма элементов в каждом из них будет нечетна. В этом случае выведите «NO». Иначе выведите «YES» и любое возможное разделение массива. Посмотрите в формат вывода для более детального объяснения.

Вам необходимо ответить на q независимых запросов.

Код

#include<bits/stdc++.h>
using namespace std;
int q,n,k,a[400000],o,t;
int main()
{
	cin>>q;
	while(q--)
	{
		cin>>n>>k;
		o=0;
		for(int i=1;i<=n;i++)
		{
			cin>>t;
			if(t%2)
			{
				a[o]=i;
				o++;
			}
		}
		if(o<k||o%2!=k%2)
			cout<<"NO";
		else
		{
			cout<<"YES"<<endl;
			for(int i=0;i<k-1;i++)
				cout<<a[i]<<' ';
			cout<<n;
		}
		cout<<endl;
	}
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться