Радиотелескоп пытается получать и анализировать сигналы, поступающие из различных участков космоса, при этом различные шумы переводятся в последовательность целых неотрицательных чисел. Чисел может быть очень много, но не может быть меньше трёх. Все числа различны. Хотя бы одно из чисел нечётно.
В данных, полученных из одного участка, выделяется основное подмножество чисел. Это непустое подмножество чисел (в него могут войти как одно число, так и все поступившие числа), такое, что их сумма нечётна и максимальна среди всех возможных непустых подмножеств с нечётной суммой. Если таких подмножеств несколько, то из них выбирается то подмножество, которое содержит наименьшее количество элементов.
Вам предлагается написать программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты, приходящие из одного участка, находя основное подмножество. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество сигналов N. В каждой из последующих N строк записано одно целое неотрицательное число, не превышающее 109.
Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.
Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования.
Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
Обязательно укажите, что программа является решением задания Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Пример входных данных:
3
123
0
2
Программа должна вывести в порядке возрастания номера сигналов, которые принадлежат основному подмножеству данного участка. Нумерация элементов последовательности ведётся с единицы. Пример выходных данных для приведённого выше примера входных данных: 1 3.
В данных, полученных из одного участка, выделяется основное подмножество чисел. Это непустое подмножество чисел (в него могут войти как одно число, так и все поступившие числа), такое, что их сумма нечётна и максимальна среди всех возможных непустых подмножеств с нечётной суммой. Если таких подмножеств несколько, то из них выбирается то подмножество, которое содержит наименьшее количество элементов.
Вам предлагается написать программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты, приходящие из одного участка, находя основное подмножество. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество сигналов N. В каждой из последующих N строк записано одно целое неотрицательное число, не превышающее 109.
Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.
Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования.
Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
Обязательно укажите, что программа является решением задания Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Пример входных данных:
3
123
0
2
Программа должна вывести в порядке возрастания номера сигналов, которые принадлежат основному подмножеству данного участка. Нумерация элементов последовательности ведётся с единицы. Пример выходных данных для приведённого выше примера входных данных: 1 3.
💡 Пошаговый разбор и решение:
Основное подмножество состоит из всех значений сигналов, кроме 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 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 j) AND ((c MOD 2 <>0) OR (i <> k)) THEN
PRINT i
NEXT i
END
Пример решения задачи A на языке Паскаль.
var
a: array[1..10000] of integer; {исходные данные}
min: integer; {минимальное нечётное число}
N: integer; {количество чисел}
sum: integer; {максимальная сумма}
i: integer;
begin
readln(N);
min := 1000000001;
sum := 0;
for i := 1 to N do readln(a[i]);
for i := 1 to N do begin
sum := sum + a[i];
if (a[i] mod 2 <> 0) and (a[i] min) and (a[i]<>0) then write(i, ' ');
if sum mod 2 <> 0 then
for i := 1 to N do
if (a[i]<>0) then write(i, ' ');
end.
Программа читает все входные данные один раз, не запоминая все входные данные в массиве, размер которого равен 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 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 j) AND ((c MOD 2 <>0) OR (i <> k)) THEN
PRINT i
NEXT i
END
Пример решения задачи A на языке Паскаль.
var
a: array[1..10000] of integer; {исходные данные}
min: integer; {минимальное нечётное число}
N: integer; {количество чисел}
sum: integer; {максимальная сумма}
i: integer;
begin
readln(N);
min := 1000000001;
sum := 0;
for i := 1 to N do readln(a[i]);
for i := 1 to N do begin
sum := sum + a[i];
if (a[i] mod 2 <> 0) and (a[i] min) and (a[i]<>0) then write(i, ' ');
if sum mod 2 <> 0 then
for i := 1 to N do
if (a[i]<>0) then write(i, ' ');
end.
📚 Похожие разобранные задания по предмету:
ID 32754 • Задание №16
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик | Python
SUB F(n)
IF n
Паск...
ID 140555 • Задание №8
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для о...
Официальные критерии проверки ФИПИ:
Критерии проверки:
Критерии оценивания выполнения задания | Баллы
Критерии оценивания задания А |
Программа решает поставленную задачу для любых соответствующих условию входных данных. Например, допускается переборное решение, аналогичное приведённой выше Программе 1.
Допускается до семи синтаксических и приравненных к ним ошибок (см. критерии оценивания задания Б на 4 балла).
Допускается до двух содержательных ошибок, описанныхв критериях оценивания задания Б на 3 балла
| 2
Не выполнены условия, позволяющие поставить 2 балла.
Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может быть представлена отдельными фрагментами, без ограничений на количество синтаксических и содержательных ошибок. 1 балл ставится также за решения, верные лишь в частных случаях
| 1
Не выполнены критерии, позволяющие поставить 1 или 2 балла | 0
Максимальный балл для задания А | 2
Критерии оценивания выполнения задания Б | Баллы
Программа правильно работает для любых соответствующих условию входных данных и при этом эффективна как по времени, так и по памяти, т.е. не используются массивы и другие структуры данных, размер которых зависит от количества входных элементов, а время работы пропорционально этому количеству. Возможно использование массивов и динамических структур данных (например, контейнеры STL в программе на языке С++) при условии, что в них в каждый момент времени хранится фиксированное количество элементов, требующих для хранения меньше 1кб (минимально необходимое количество — шесть; допускается решение с запасом).
Программа может содержать не более трёх синтаксических ошибок следующих видов:
— пропущен или неверно указан знак пунктуации (запятая, точка с запятой, скобки и т.д.);
— неверно написано или пропущено служебное слово языка программирования;
— не описана или неверно описана переменная;
— применяется операция, недопустимая для соответствующего типа данных. К синтаксическим ошибкам приравнивается использование неверного типа данных (например, использование целого типа вместо вещественного для представления данных при вводе и обработке).
Если одна и та же ошибка встречается несколько раз, она считается за одну ошибку
| 4
Не выполнены условия, позволяющие поставить 4 балла.
Программа правильно работает для любых соответствующих условию входных данных, время работы пропорционально количеству входных элементов. Размер используемой памяти не имеет значения и может зависеть от объёма входных данных. В частности, допускается использование одного или нескольких массивов размера N (как в приведённой выше программе 3).
Программа может содержать не более пяти синтаксических и приравненных к ним ошибок, описанных в критериях на 4 балла.
Кроме того, допускается наличие не более одной содержательной ошибки из числа следующих:
— неверная инициализация при поиске минимального значения;
— неверная обработка начальных элементов данных, которая может, например, привести к получению ошибочного ответа при 15
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет. Например, допускается переборное решение, аналогичное приведённой выше программе 4. Допускается до семи синтаксических и приравненных к ним ошибок (см. критерии на 4 балла).
Допускается до двух содержательных ошибок, описанных в критериях на 3 балла
| 2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может быть представлена отдельными фрагментами, без ограничений на количество синтаксических и содержательных ошибок. 1 балл ставится также за решения, верные лишь в частных случаях | 1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла | 0
Максимальный балл для задания Б | 4
Итоговый максимальный балл | 4
Критерии оценивания выполнения задания | Баллы
Критерии оценивания задания А |
Программа решает поставленную задачу для любых соответствующих условию входных данных. Например, допускается переборное решение, аналогичное приведённой выше Программе 1.
Допускается до семи синтаксических и приравненных к ним ошибок (см. критерии оценивания задания Б на 4 балла).
Допускается до двух содержательных ошибок, описанныхв критериях оценивания задания Б на 3 балла
| 2
Не выполнены условия, позволяющие поставить 2 балла.
Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может быть представлена отдельными фрагментами, без ограничений на количество синтаксических и содержательных ошибок. 1 балл ставится также за решения, верные лишь в частных случаях
| 1
Не выполнены критерии, позволяющие поставить 1 или 2 балла | 0
Максимальный балл для задания А | 2
Критерии оценивания выполнения задания Б | Баллы
Программа правильно работает для любых соответствующих условию входных данных и при этом эффективна как по времени, так и по памяти, т.е. не используются массивы и другие структуры данных, размер которых зависит от количества входных элементов, а время работы пропорционально этому количеству. Возможно использование массивов и динамических структур данных (например, контейнеры STL в программе на языке С++) при условии, что в них в каждый момент времени хранится фиксированное количество элементов, требующих для хранения меньше 1кб (минимально необходимое количество — шесть; допускается решение с запасом).
Программа может содержать не более трёх синтаксических ошибок следующих видов:
— пропущен или неверно указан знак пунктуации (запятая, точка с запятой, скобки и т.д.);
— неверно написано или пропущено служебное слово языка программирования;
— не описана или неверно описана переменная;
— применяется операция, недопустимая для соответствующего типа данных. К синтаксическим ошибкам приравнивается использование неверного типа данных (например, использование целого типа вместо вещественного для представления данных при вводе и обработке).
Если одна и та же ошибка встречается несколько раз, она считается за одну ошибку
| 4
Не выполнены условия, позволяющие поставить 4 балла.
Программа правильно работает для любых соответствующих условию входных данных, время работы пропорционально количеству входных элементов. Размер используемой памяти не имеет значения и может зависеть от объёма входных данных. В частности, допускается использование одного или нескольких массивов размера N (как в приведённой выше программе 3).
Программа может содержать не более пяти синтаксических и приравненных к ним ошибок, описанных в критериях на 4 балла.
Кроме того, допускается наличие не более одной содержательной ошибки из числа следующих:
— неверная инициализация при поиске минимального значения;
— неверная обработка начальных элементов данных, которая может, например, привести к получению ошибочного ответа при 15
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет. Например, допускается переборное решение, аналогичное приведённой выше программе 4. Допускается до семи синтаксических и приравненных к ним ошибок (см. критерии на 4 балла).
Допускается до двух содержательных ошибок, описанных в критериях на 3 балла
| 2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может быть представлена отдельными фрагментами, без ограничений на количество синтаксических и содержательных ошибок. 1 балл ставится также за решения, верные лишь в частных случаях | 1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла | 0
Максимальный балл для задания Б | 4
Итоговый максимальный балл | 4
🔗 Другие задания линии №27 по предмету Информатика:
ID 34669
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой ...
ID 34670
Последовательность натуральных чисел характеризуется числом Х — наибольшим числом, кратным 14 ...
ID 34671
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются ...
ID 34672
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последо...
ID 34673
На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары...