Задание № 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.