СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
Информатика
Cайты, меню, вход, новости


Задания
Версия для печати и копирования в MS Word
Задание 27 № 5567

На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы — это целое число (положительное, отрицательное или 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.


Аналоги к заданию № 5375: 5407 5439 5535 5567 Все

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Дальний Восток. Вариант 5.