Решение задачи Премьер-министр с Codeforces

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

Алиса — лидер Государственной рефакторинговой партии, и она близка к тому, чтобы стать Премьер-министром.

Только что прошли выборы. Всего было n партий, последовательно пронумерованных от 1 до n. i-я партия получила ai мест в парламенте.

Партия Алисы имеет номер 1. Чтобы стать Премьер-министром, ей нужно создать коалицию, которая состоит из ее партии и, возможно, других партий. Есть два ограничения на создание коалиции:

Коалиция должна иметь большинство в парламенте, другими словами, суммарное количество мест всех партий коалиции должно быть строго больше половины мест в парламенте. Например, если в парламенте 200 (или 201) мест, то большинство — это 101 и больше мест.
Партия Алисы должна иметь хотя бы в 2 раза больше мест в парламенте, чем любая другая партия в коалиции. Например, чтобы взять в коалицию партию с 50 местами, у партии Алисы должно быть как минимум 100 мест.
Например, если n=4 и a=[51,25,99,25] (обратите внимание, что партия Алисы получила 51 место), то следующий набор [a1=51,a2=25,a4=25] может являться коалицией, так как удовлетворяет обоим условиям, а следующие наборы — нет:

[a2=25,a3=99,a4=25] — так как не содержит партию Алисы;
[a1=51,a2=25] — так как коалиция должна иметь строгое большинство мест;
[a1=51,a2=25,a3=99] — так как партия Алисы должна иметь хотя бы в 2 раза больше мест в парламенте, чем любая другая партия в коалиции.
Алиса может не минимизировать количество партий в коалиции. Она может пригласить сколько угодно партий, если оба условия будут выполнены. С другой стороны, если партия Алисы имеет достаточное количество мест в парламенте для выполнения первого условия, она может и не приглашать другие партии.

Обратите внимание, что Алиса может либо взять всю партию в коалицию, либо никого из той партии. Нельзя взять только несколько (не всех) депутатов (мест) в другой партии. Другими словами, если она берет партию в коалицию, то она берет всех ее депутатов.

Найдите любую подходящую коалицию.

Код 

#include<bits/stdc++.h>
using namespace std;
int n,a[200],p,c,k=1,s;
int main()
{
	cin >> n;
	cin >> p;
	c = p;
	s = c;
	for(int i = 2; i <= n;i++){
		cin >> a[i];
		s += a[i];
		if(a[i] <= p / 2){
			c += a[i];
			k++;
		}
	}
	if(c > s/2)
	{
		cout << k << endl << 1 << ' ';
		for(int i = 2; i <= n; i++){
			if(a[i] <= p/2)
				cout << i << ' ';
		}
	}
	else
		cout << 0;
	return 0;
}

         

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




Комментарии

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


© 2020 HSECODES [email protected] Карта сайта