По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное... | Яндекс.Репетитор

Задание#T25502

По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают

Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности – наибольшее число удовлетворяющее следующим условиям:

– произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел; допускаются произведения различных элементов последовательности, равных по величине);
делится на

Если такого числа нет, то контрольное значение полагается равным

В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.

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

Вычисленное контрольное значение: …
Контроль пройден (или – Контроль не пройден)

Перед текстом программы кратко опишите используемый Вами алгоритм решения.

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

В последней строке записано контрольное значение.

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

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

Вычисленное контрольное значение: 21000
Контроль пройден

Показать разбор

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

(допускаются иные формулировки ответа, не искажающие его смысла)

Произведение двух чисел делится на если:

один из сомножителей делится на (второй может быть любым) либо
ни один из сомножителей не делится на причём один из сомножителей делится на а другой – на

Поэтому программа, вычисляющая кодовое число, может работать так.

Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин:

– самое большое число, кратное но не кратное

– самое большое число, кратное

– самое большое число среди всех элементов последовательности, отличное от

(если число

встретилось более одного раза и оно же является максимальным, то

После того как все данные прочитаны, искомое контрольное значение вычисляется как максимум из произведений

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

Кроме того, приведён пример программы на языке Бейсик, которая правильно решает задачу, но использует алгоритм, немного отличающийся от описанного выше. Возможны и другие правильные алгоритмы.

Допускаются решения, записанные на других языках программирования.

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

var M7,M3,M21,R,MAX,dat,res,i,N: longint;
begin
  M7 := 0;
  M3 := 0;
  M21 := 0;
  MAX := 0;
  readln(N);
  for i := 1 to N do
  begin
    readln(dat);
    if ((dat mod 7) = 0) and ((dat mod 3) > 0) and (dat > M7) then
      M7 := dat;
    if ((dat mod 3) = 0) and ((dat mod 7) > 0) and (dat > M3) then
      M3 := dat;
    if (dat mod 21 = 0) and (dat > M21) then
    begin
      if M21 > MAX then MAX := M21;
      M21 := dat
    end
    else
    if dat > MAX then
      MAX := dat;
  end;
  readln(R);
  if (M7*M3 < M21*MAX) then
    res := M21*MAX
  else
    res := M7*M3;
  writeln('Вычисленное контрольное значение: ',res);
  if R = res then writeln('Контроль пройден')
             else writeln('Контроль не пройден');
end.

Указания по оцениванию

балла ставится за эффективную и правильно работающую программу, которая, возможно, содержит до трёх синтаксических ошибок.

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

балла ставится, если программа неэффективна по времени работы (перебираются все возможные пары элементов), или в программе две содержательные ошибки, либо шесть-семь синтаксических ошибок.

балл ставится, если программа написана неверно, но из описания алгоритма и общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи.

Далее уточняются перечисленные выше критерии.

Порядок назначения третьего эксперта

В соответствии с Порядком проведения государственной итоговой аттестации по образовательным программам среднего общего образования (приказ Минобрнауки России от

г.

зарегистрирован Минюстом России

г.

« По результатам первой и второй проверок эксперты независимо друг от друга выставляют баллы за каждый ответ на задания экзаменационной работы ЕГЭ с развернутым ответом...»;

« В случае существенного расхождения в баллах, выставленных двумя экспертами, назначается третья проверка. Существенное расхождение в баллах определено в критериях оценивания по соответствующему учебному предмету.

Эксперту, осуществляющему третью проверку, предоставляется информация о баллах, выставленных экспертами, ранее проверявшими экзаменационную работу».

Если расхождение составляет и более балла за выполнение любого из заданий, то третий эксперт проверят ответы только на те задания, которые вызвали столь существенное расхождение.

Критерии оценки

4 баллаПрограмма правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству.
Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов:
— пропущен или неверно указан знак пунктуации;
— неверно написано или пропущено зарезервированное слово языка программирования;
— не описана или неверно описана переменная;
— применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку).

3 баллаНе выполнены условия, позволяющие поставить балла.
Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел.
Количество синтаксических ошибок («описок») указанных выше видов – не более пяти.
Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве или другой структуре данных (контейнер

или

в С++)).
Допускается ошибка при вводе данных, неверный или неполный вывод результатов или неверная работа программы в «экзотических» ситуациях. Например, при использовании -битного целого (

в BPascal или Qbasic) умножаются два числа этого типа (результат по условию может не помещаться в бит).
Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов ошибок.
1. Допущена ошибка при инициализации максимумов.
2. Неверно обрабатывается ситуация, когда один или несколько максимумов не определены.
3. Неверно обрабатывается ситуация, когда максимальное произведение получается умножением одинаковых чисел (но разных элементов входной последовательности).
4. При вычислении максимумов учитываются произведения вида

5. Допущен выход за границу массива.
6. Допущена ошибка в реализации алгоритма сортировки.
7. Используется знак “” вместо “

”,

вместо

и т.п.

2 баллаНе выполнены условия, позволяющие поставить или балла.
Программа работает в целом верно, эффективно или нет, но в реализации алгоритма содержится до двух содержательных ошибок, допустимые виды ошибок перечислены в критериях на балла.
Количество синтаксических «описок» не должно быть более семи. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве (ниже – количество прочитанных чисел), и перебираются все возможные пары элементов последовательности.
Например, так:
max := 0;
for i := 1 to n - 1 do
for j := i + 1 to n do

if ((a[i]*a[j]) mod 21 = 0) and

((a[i]*a[j]) > max) then

max := a[i]*a[j];

1 баллНе выполнены условия, позволяющие поставить

или балла. При этом выполнено одно из двух условий.
1. Из описания алгоритма и общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи.
2. Программа правильно работает в одном из важных частных случаев, например в случае, когда искомое произведение – это произведение наибольшего числа, которое делится на и наибольшего числа, которое делится на
Допускается любое количество синтаксических ошибок.

0 балловНе выполнены критерии, позволяющие поставить

или балла.

Это задание в разделах:

ЕГЭ-2014 - Архив

Задание#T25502

Это задание в разделах:

Рекомендованные задания