Задание № 7201

В химической лаборатории для большого количества органических молекул измеряется количество входящих в молекулу атомов углерода — целое неотрицательное число, которое будем называть С-индексом молекулы. Исследуемых молекул может быть очень много, но не может быть меньше трёх. С-индексы во всех молекулах различны. С-индекс, по крайней мере одной молекулы, является нечётным числом.

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

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

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

\n

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

3

0

13

202

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

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

2

3


Решать другие задания по теме: Об­ра­бот­ка символьных строк

Показать ответ
Комментарий:

Содержание верного ответа

Основное множество состоит из всех значений С-индексов, кроме 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 nmin = 0 k = 0 j = 0 cnt = 0FOR i = 1 ТО n 	INPUT a	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 iFOR i = 1 TO n	IF (i <> j) AND ((cnt MOD 2 <> 0) OR (i <> k)) THEN PRINT i NEXT i END
 Ответ:

Нашли ошибку в задании? Выделите фрагмент и нажмите Ctrl + Enter.