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