Решение номера 7608 ФИПИ

На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы – это целое неотрицательное число. Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны.

 

При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это непустое подмножество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), такое, что сумма значений скоростей у него чётна и максимальна среди всех возможных непустых подмножеств с чётной суммой. Если таких подмножеств несколько, то из них выбирается то подмножество, которое содержит наименьшее количество элементов.

 

Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, BorlandPascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество.

 

Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи.

 

На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое неотрицательное число, не превышающее 109. Все N чисел различны.

 

Пример входных данных:

5

123

2

1000

0

10

Программа должна вывести в порядке возрастания номера частиц, скорости которых

принадлежат основному множеству данной серии. Нумерация частиц ведётся с единицы.

 

Пример выходных данных для приведённого выше примера входных данных:

2 3 5

 

Объяснение

По условию сумма скоростей множества четна, максимальна и составлена из минимального количества элементов. Сумма будет четной, если количество нечетных слагаемых четное. Если на вход подается нечетное количество нечетных элементов, то мы должны выбрать минимальное из всех этих элементов и не вписывать его в множество. Четные слагаемые не влияют на дальнейшую четность или нечетность суммы, значит четные элементы всегда будут в множестве. Так как множество составляется из минимального количества элементов, а сумма элементов множества должна быть максимальной, то в него не будет входить ноль и, при необходимости, наименьший нечетный элемент. По условию все скорости частиц различны, значит если в последовательности встречается ноль, то он встречается в первый и последний раз (то же самое и с минимальным нечетным числом). Итак, в программе мы будем хранить 3 переменные: минимальное нечетное число (m), номер минимального нечетного числа (min_number) и номер нуля (zero_number). Чтобы определить четное или нечетное количество нечетных элементов введем логическую переменную flag. Четному количеству будет соответствовать True, а нечетному False. Изначально вводим True и с каждым новым входом нечетного числа меняем значение переменной на противоположное (Если было True, то меняем его на False и наоборот). В конце с помощью дополнительного цикла выводим номера, исключая номер нуля и (или) номер максимального отрицательного числа, если это понадобится.

 

Решение на языке Паскаль

Показать решение

 

Решение на языке Python

Показать решение

 

Похожие задачи: 7672, 7640

Раздел: Программирование

 

Оставить комментарий