Решение задачи Премьер-министр с 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 раза больше мест в парламенте, чем любая другая партия в коалиции.
Алиса может не минимизировать количество партий в коалиции. Она может пригласить сколько угодно партий, если оба условия будут выполнены. С другой стороны, если партия Алисы имеет достаточное количество мест в парламенте для выполнения первого условия, она может и не приглашать другие партии.
Обратите внимание, что Алиса может либо взять всю партию в коалицию, либо никого из той партии. Нельзя взять только несколько (не всех) депутатов (мест) в другой партии. Другими словами, если она берет партию в коалицию, то она берет всех ее депутатов.
Найдите любую подходящую коалицию.
Только что прошли выборы. Всего было 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 раза больше мест в парламенте, чем любая другая партия в коалиции.
Алиса может не минимизировать количество партий в коалиции. Она может пригласить сколько угодно партий, если оба условия будут выполнены. С другой стороны, если партия Алисы имеет достаточное количество мест в парламенте для выполнения первого условия, она может и не приглашать другие партии.
Обратите внимание, что Алиса может либо взять всю партию в коалицию, либо никого из той партии. Нельзя взять только несколько (не всех) депутатов (мест) в другой партии. Другими словами, если она берет партию в коалицию, то она берет всех ее депутатов.
Найдите любую подходящую коалицию.