|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Алиса — лидер Государственной рефакторинговой партии, и она близка к тому, чтобы стать Премьер-министром.
Только что прошли выборы. Всего было 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
раза больше мест в парламенте, чем любая другая партия в коалиции.
Алиса может не минимизировать количество партий в коалиции.Она может пригласить сколько угодно партий, если оба условия будут выполнены. С другой стороны, если партия Алисы имеет достаточное количество мест в парламенте для выполнения первого условия, она может и не приглашать другие партии.
Обратите внимание, что Алиса может либо взять всю партию в коалицию, либо никого из той партии. Нельзя взять только несколько (не всех) депутатов (мест) в другой партии. Другими словами, если она берет партию в коалицию, то она берет всех ее депутатов.
Найдите любую подходящую коалицию.
Входные данные:
Первая строка содержит одно целое число n
(2<=n<=100) — количество партий.
Вторая строка содержит n
целых чисел a1,a2,…,an
(1<=a(i)<=100) — количество мест i
-й партии в парламенте.
Выходные данные:
Если невозможно создать такую коалицию, то выведите 0.
В противном случае, пусть k
(1<=k(i)<=n) — количество партий в коалиции (Алиса может не минимизировать количество партий в коалиции), а c1,c2,…,ck
(1<=c(i)<=n) — номера этих партий. В первой строке выведите k
, а во второй c1,c2,…,ck.
Вы можете выводить партии в любом порядке. Партия Алисы (номер 1
) должна быть в этом списке. Если существует несколько решений, выведите любое из них.
1)input:
3
100 50 50
1)output:
3
1 2 3
2)input:
3
80 60 60
2)output:
0
3)input:
2
6 5
3)output:
1
1
Примечание
В первом примере Алиса пригласила вторую партию. Обратите внимание, она также могла пригласить как третью партию, так и обе эти партии. Но она не смогла бы стать Премьер-министром, не приглашая ни одну партию, потому что 100
мест мало для того, чтобы гарантировать большинство в парламенте, где 200
мест.
Во втором примере невозможно создать коалицию, так как любая партия слишком большая для того, чтобы пригласить ее в коалицию.
В третьем примере одной лишь партии Алисы достаточно для коалиции.
Для отправки решений необходимо выполнить вход.
|