На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы — это целое число (положительное, отрицательное или 0). Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны.
При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это такое непустое множество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), для которого произведение скоростей является максимальным среди всех возможных множеств. При нахождении произведения знак числа учитывается. Если есть несколько таких множеств, то основным считается то, которое содержит наибольшее количество элементов.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи.
На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое число, по абсолютной величине не превышающее 109.
Пример входных данных:
5
123
2
-1000
0
10
Программа должна вывести в порядке возрастания номера частиц, скорости которых принадлежат основному множеству данной серии. Нумерация частиц ведётся с единицы.
Пример выходных данных для приведённого выше примера входных данных:
1 2 5
Если n > 2, то тогда нужно вывести позиции всех положительных чисел и, если отрицательных чисел чётное количество, то позиции всех отрицательных чисел, а если нечётное, то всех отрицательных чисел кроме одного - самого маленького по модулю. Почему так? При добавлении положительного числа произведение не уменьшается, а количество чисел во множестве увеличивается, значит, все положительные числа должны попасть во множество. Произведение чётного количества отрицательных чисел положительно и равно произведению модулей соответствующих чисел. Когда же чисел нечётное количество, произведение отрицательное. Именно поэтому одно отрицательное число нужно убрать. А чтобы произведение получилось максимальное, убрать нужно минимальное по модулю число. Для получения непосредственно ответа будем перебирать все числа от 1 до n и выводить текущее число, если оно не равно позиции нуля в списке. А если отрицательных чисел нечётное количество, то оно также должно быть не равно позиции минимального отрицательного числа.
Ниже приведён код решения на языке Pascal версии 2.6.2.
var n, i, cur, zeroInd, cntNeg, max, maxInd : longint;
begin
max := low(longint);
readln(n);
for i := 1 to n do
begin
readln(cur);
if cur = 0 then
zeroInd := i;
if cur < 0 then
begin
inc(cntNeg);
if cur > max then
begin
max := cur;
maxInd := i;
end;
end;
end;
if cntNeg mod 2 = 0 then
maxInd := 0;
for i := 1 to n do
if (i <> zeroInd) and (i <> maxInd) then
write(i, ' ');
end.