На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы — это целое число (положительное, отрицательное или 0). Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны. В серии обязательно присутствует хотя бы одна частица с отрицательной скоростью.
При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это такое непустое множество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), для которого произведение скоростей является минимальным среди всех возможных подмножеств. При нахождении произведения знак числа учитывается. Если есть несколько таких множеств, то берётся то, которое содержит наибольшее количество элементов.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество.
Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи.
На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое число, по абсолютной величине не превышающее 109. Все N чисел различны.
Пример входных данных:
5
123
2
−1000
0
10
Программа должна вывести в порядке возрастания номера частиц, скорости которых принадлежат основному множеству данной серии. Нумерация частиц ведётся с единицы.
Пример выходных данных для приведённого выше примера входных данных:
1 2 3 5
Ясно, что основное множество состоит из всех положительных скоростей и всех отрицательных скоростей, если отрицательных скоростей нечётное число. Если же отрицательных скоростей чётное число, то основное множество состоит из всех положительных скоростей и всех отрицательных скоростей, кроме частицы имеющей самую маленькую по модулю отрицательную скорость.
Приведённая ниже программа в переменной parity хранит число частиц, имеющих отрицательную скорость. В переменной ineg хранит порядковый номер наименьшего по модулю отрицательного числа. В переменной zero хранится порядковый номер нуля, если он присутствует во входных данных.
Программа подсчитывает число частиц, имеющих отрицательную скорость и фиксирует номер наименьшего отрицательного числа. Также программа фиксирует присутствие нуля во входных данных. Если число частиц, имеющих отрицательную скорость чётно, то выводятся все номера частиц, кроме номера частицы с самой маленькой по модулю отрицательной скоростью. В противном случае выводятся номера всех частиц. Номер частицы, имеющей нулевую скорость не выводится, если такая частица есть.
Пример программы на языке Паскаль:
program N_27;
var
N: Word;
a: LongInt; {текущее значение скорости}
neg: LongInt; {значение наименьшей по модулю отрицательной скорости}
ineg: Word; {номер частицы, имеющей минимальную по модулю отрицательную скорость}
zero: Word; {номер частицы, имеющей нулевую скорость}
parity: Word; {число частиц с отрицательной скоростью}
i: integer;
begin
neg:=-10*10*10*10*10*10*10*10*10-1;
ineg:=0;
zero:=0;
parity:=0;
readln(N);
for i:=1 to N do
begin
readln(a);
if a<0 then
begin
parity:=parity+1;
if a > neg then
begin
neg:=a;
ineg:=i;
end;
end;
if a=0 then zero:=i;
end;
for i:=1 to N do
begin
if ((parity mod 2=0) and (i<>ineg) and (i<>zero)) then write(i,' ');
if ((parity mod 2=1) and (i<>zero)) then write(i,' ');
end;
end.
Примечание.
Ясно, что в данной программе можно избежать 2N последних проверок, если при помощи нескольких условий проверить как соотносятся номера частиц, имеющих нулевую и минимальную по модулю отрицательную скорость, а затем вывести номера всех частиц кроме этих двух, циклами типа:
for i:=1 to ineg-1 do write(i,' ' );
for i:=ineg+1 to zero-1 do write(i,' ' );
for i:=zero+1 to N do write(i,' ' );
Здесь рассмотрен самый простой случай, когда исключаемые номера не равны единице и друг другу.
Приводим эффективное решение Игоря Кудашева на Python 3.
n = int(input())
s = 0
d = 10001
for i in range(n):
a, b = map(int,input().split())
if a > b:
ma = a
mi = b
else:
ma = b
mi = a
s += ma
if (ma - mi) % 3 > 0 and ma - mi < d: d = ma - mi
if s % 3 == 0:
if d > 10000: s = 0
else: s -= d
print(s)