На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы — это целое число (положительное, отрицательное или 0). Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны. При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это такое непустое множество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), для которого произведение скоростей является максимальным среди всех возможных множеств. При нахождении произведения знак числа учитывается. Если есть несколько таких множеств, то основным считается то, которое содержит наибольшее количество элементов.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи.
На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое число, по абсолютной величине не превышающее 109.
Пример входных данных:
5
123
2
-1000
0
10
Программа должна вывести в порядке возрастания номера частиц, скорости которых принадлежат основному множеству данной серии. Нумерация частиц ведётся с единицы.
Пример выходных данных для приведённого выше примера входных данных:
1 2 5
Основное множество состоит из всех значений скоростей, кроме 0. если он встречается, и кроме минимальной по модулю отрицательной скорости, если отрицательных скоростей нечётное число.
Программа читает все входные данные один раз. не запоминая все входные данные в массиве, размер которого равен N. Во время чтения данных запоминается номер 0, если он встретился (по условию все значения различны, поэтому 0 встречается не больше одного раза), подсчитывается количество отрицательных значений и шлется минимальное по модулю отрицательное значение. После окончания ввода распечатываются все номера, кроме номера 0 и номера минимального по модулю отрицательного значения, но только в случае, если их нечётное число.
Ниже приведены примеры решения задания на языках Паскаль и Бейсик.
var n, i, j, к, с, min, a: longint;
begin
readln(n);
min := 1000000001;
k := 0;
j := 0 ;
с := 0;
for i := 1 to n do
begin
readln(a);
if a = 0 then
j := i;
if a < 0 then
begin
с := с + 1;
if a < min
then
begin
min := a;
k := i;
end;
end;
end;
for i :=1 to n do
if (i <> j) and ((c mod 2 = 0) or (i <> k)) then write(i, ' ');
end.
Пример правильной и эффективной программы на языке Бейсик:
INPUT n
min = 0
k = 0
j = 0
c = 0
FOR i = 1 TO n
INPUT а
IF а = 0 THEN j = i
IF а < 0 THEN
с = с + 1
IF (min = 0) OR (a < min) THEN
min = а
k = i
END IF
END IF
NEXT i
FOR i = 1 TO n
IF (i <> j) AND ((c MOD 2 = 0) OR (i <> k)) THEN PRINT i
NEXT i
END