На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы – это целое число (положительное, отрицательное или 0). Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны. В серии обязательно присутствует хотя бы одна частица с отрицательной скоростью.
При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это такое непустое подмножество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), для которого произведение скоростей является минимальным среди всех возможных подмножеств. При нахождении произведения знак числа учитывается. Если есть несколько таких множеств, то берётся то, которое содержит наибольшее количество элементов.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, BorlandPascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество.
Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи.
На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое число, по абсолютной величине не превышающее 109. Все N чисел различны.
Пример входных данных:
5
123
2
-1000
0
10
Программа должна вывести в порядке возрастания номера частиц, скорости которых принадлежат основному множеству данной серии. Нумерация частиц ведётся с единицы.
Пример выходных данных для приведённого выше примера входных данных:
1 2 3 5
Объяснение
Так как в последовательности есть как минимум одно отрицательное значение, то очевидно, что конечное произведение должно быть меньше нуля. Значит количество отрицательных сомножителей в множестве должно быть нечетным. Если на вход поступает четное количество отрицательных чисел, то нам надо выбрать номер максимального отрицательного числа и не включать его в последовательность. Положительные сомножители не влияют на знак конечного произведения, значит, чтобы произведение было как можно меньше, мы будем просто включать их в множество. По условию все скорости частиц различны, значит, если где-то в последовательности встречается ноль, то он встречается в первый и последний раз. Его в множество мы включать не будем, так как любое число умноженное на ноль дает ноль и произведение не будет наименьшим. Итак, в программе мы будем хранить 3 переменные: максимальное отрицательное число (m), номер максимального отрицательного числа (max_number) и номер нуля (zero_number). Чтобы определить четное или нечетное количество отрицательных переменных введем логическую переменную flag. Четному количеству будет соответствовать True, а нечетному False. Изначально вводим True и с каждым новым входом отрицательного числа меняем значение переменной на противоположное (Если было True, то меняем его на False и наоборот). В конце с помощью дополнительного цикла выводим номера, исключая номер нуля и (или) номер максимального отрицательного числа, если это понадобится.
Решение на языке Паскаль
Показать решение|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
var N: biginteger; //Количество чисел i: biginteger; //Счётчик m: int64; //Максимальное отрицательное число a: int64; //Очередное число max_number: biginteger; //Номер максимального отрицательного числа zero_number: biginteger; //Номер нуля flag: boolean; //Логическая переменная для определения знака получаемой суммы begin m := -1000000001; flag := true; zero_number := 0; max_number :=0; readln(N); i := 1; while i <= N do begin readln(a); if a = 0 then zero_number := i; if a < 0 then begin flag := not (flag); if a > m then begin m := a; max_number := i; end; end; i := i + 1; end; i := 1; while i <= N do begin if (i <> zero_number) and ((i <> max_number) or (flag = false)) then write(i, ' '); i := i + 1; end; end. |
Решение на языке Python
Показать решение|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
zero_number = 0 max_number = 0 m = -(10 ** 9) - 1 flag = True N = int(input()) for i in range(1, N + 1): a = int(input()) if a == 0: zero_number = i if a < 0: flag = not flag if a > m: m = a max_number = i for i in range(1, N + 1): if i != zero_number and (i != max_number or flag == False): print(i, end = ' ') |
Раздел: Программирование