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


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

На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы — это неотрицательное целое число. Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны. При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это такое непустое множество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), такое, что сумма значений скоростей у него чётна и максимальна среди всех возможных непустых подмножеств с чётной суммой. Если есть несколько таких множеств, то основным считается то, которое содержит наименьшее количество элементов.

 

Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи.

 

На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое неотрицательное число, не превышающее 109. Все N чисел различны. Хотя бы одно из чисел нечётно.

 

Пример входных данных:

 

5

123

2

1000

0

10

 

Программа должна вывести в порядке возрастания номера частиц, скорости которых принадлежат основному множеству данной серии. Нумерация частиц ведётся с единицы.

 

Пример выходных данных для приведённого выше примера входных данных: 2 3 5.

Решение.

Основное множество состоит из всех значений скоростей, кроме 0, если он встречается, и кроме минимального нечётного значения, если таких значений нечётное число.

Программа читает все входные данные один раз. не запоминая все входные данные в массиве, размер которого равен N. Во время чтения данных запоминается номер 0. если он встретится (по условию все значения различны, поэтому 0 встречается не больше одного раза), подсчитывается количество нечётных значений и ищется минимальное нечётное значение. После окончания ввода распечатываются все номера, кроме номера 0 и номера минимального нечётного значения, но только в случае, если их количество нечётно.

Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая. Ниже приведены примеры решения задания на языках Паскаль и Бейсик. Допускаются решения, записанные на других языках программирования.

 

Пример правильной и эффективной программы на языке Паскаль

var n,i,j,k,c,min,a: longint;

begin

readln(n);

min := 1000000001;

k := 0;

j := 0;

c := 0;

for i:=1 to n do begin

readln(a);

if a = 0

then j := i;

if a mod 2 <> 0

then

begin

c := c + 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 a

IF a = 0 THEN j = i

IF a mod 2 <> 0 THEN

c = c + 1

IF (min = 0) OR (a < min) THEN

min = a

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

 

Примечание. Решение построено в предположении, что ноль не входит в основное подмножество.


Аналоги к заданию № 5471: 5599 5695 Все

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