На вход программы поступает последовательность из N целых положительных чисел. Известно, что все числа в последовательности различны. Необходимо составить программу, которая подсчитывает количество пар... | Яндекс.Репетитор

Задание#T8658

На вход программы поступает последовательность из целых положительных чисел. Известно, что все числа в последовательности различны. Необходимо составить программу, которая подсчитывает количество пар различных элементов последовательности, произведение которых делится на Элементы пары не обязательно должны стоять в последовательности рядом, порядок элементов в паре не важен.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел

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

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

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

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

Пояснение. Из пяти заданных чисел можно составить попарных произведений:

Из них на делятся произведений

Требуется написать эффективную по времени и по памяти программу для решения описанной задачи.

Программа считается эффективной по времени, если при увеличении количества исходных чисел в раз время работы программы увеличивается не более чем в раз.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает килобайта и не увеличивается с ростом

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

Максимальная оценка за правильную программу, эффективную только по времени – балла.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – балла.

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

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

Укажите использованный язык программирования и его версию.

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

Содержание верного ответа и указания по оцениванию

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

Описание алгоритма. Произведение двух чисел делится на если выполнено одно из следующих условий (условия не могут выполняться одновременно).

Оба сомножителя делятся на
Один из сомножителей делится на , а другой не делится.
Ни один из сомножителей не делится на , но один сомножитель делится на , а другой – на .

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

– количество чисел, кратных ;
– количество чисел, кратных , но не кратных ;
– количество чисел, кратных , но не кратных .

Сами числа при этом можно не хранить. Каждое число учитывается не более чем в одном из счётчиков.

Количество пар, удовлетворяющих условию 1), можно вычислить по формуле

Количество пар, удовлетворяющих условию 2), можно вычислить по формуле

Количество пар, удовлетворяющих условию 3), можно вычислить по формуле

Поэтому искомое количество пар вычисляется по формуле

Пример правильной программы на языке PascalABC с комментариями:

var
  N: integer;   {общее количество чисел} 
  a: integer;   {очередное число} 
  n51, n17, n3: integer; {счетчики чисел, кратных 51, 17, 3} 
  k51: integer;  {количество требуемых пар, ответ} 
  i: integer; 

begin 
 readln(N); 
 n51:=0; n17:=0; n3:=0; 
 for i:=1 to N do begin 
  readln(a); 
  if a mod 51 = 0 then 
   inc(n51) 
  else if a mod 17 = 0 then 
   inc(n17) 
  else if a mod 3 = 0 then 
   inc(n3); 
 end; 
 k51 := n51*(n51-1) div 2 + n51*(N-n51) + n3*n17; 
 writeln(k51); 
end.

При таком решении каждое прочитанное число обрабатывается (делаются проверки делимости, изменяются счётчики) и после этого не хранится. Таким образом, используемая память не зависит от длины последовательности. Время обработки очередного числа фиксировано, т.е. не зависит от длины последовательности. Время заключительных вычислений по приведённой в решении формуле также не зависит от длины последовательности. Поэтому при увеличении длины последовательности в раз время работы программы увеличивается не более чем в раз. Таким образом, приведённая выше программа эффективна как по времени, так и по используемой памяти. Это решение оценивается баллами.
Общая идея решения, эффективного по времени, состоит в следующем. Просматриваем по очереди все элементы последовательности и накапливаем значения вспомогательных величин. После того как вся последовательность обработана и подсчитаны окончательные значения вспомогательных величин, по этим значениям подсчитывается искомое количество пар. При этом можно использовать и другие вспомогательные величины. Все подобные программы оцениваются в балла.
Возможно решение, основанное на описанных идеях, однако предварительно сохраняющее элементы последовательности в массив. Такое решение (если в нём нет ошибок) эффективно по времени, но неэффективно по памяти. Оно оценивается в балла.
Решение, не эффективное ни по времени, ни по памяти, запоминает входную последовательность в массиве, после чего явно перебирает все возможные пары. Такое решение оценивается в балла (см. критерии).

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

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

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

3 баллаНе выполнены условия, позволяющие поставить балла.
Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел; правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел.
Количество синтаксических ошибок («описок») указанных в критериях на балла, не более пяти.
Допускается наличие не более одной ошибки следующих видов:
допущена ошибка при вводе данных, например не считывается значение , или числа могут быть считаны, только если будут записаны в одной строке через пробел;
ошибка при инициализации или отсутствие инициализации счётчиков;
в программе перепутаны знак целочисленного деления и взятия остатка или знаки операций «равно» и «не равно», „or‟ вместо „and‟ и т.п.;
использована неверная структура проверок, в результате которой некоторые счётчики могут получить неверное значение;
получены правильные значения счётчиков (вспомогательных величин), которые в принципе позволяют получить требуемое количество пар, но формула для вычисления записана неверно (комбинаторная ошибка);
отсутствует вывод ответа, или выводится значение не той переменной;
в описании алгоритма правильно описан смысл используемых вспомогательных величин, и в программе правильно записан алгоритм вычисления искомого количества пар, исходя из этих величин, однако при вычислении одной из вспомогательных величин допущена ошибка;
использована одна переменная (или константа) вместо другой;
используется один знак операции вместо другого;

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

балла также ставится за программу, в которой нет содержательных ошибок, но используемая память зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных)

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

k := 0;
for i := 1 to n - 1 do

for j := i + 1 to n do

if a[i]*a[j] mod 51 = 0 then

k := k + 1;
writeln(k);

В реализации переборного алгоритма не допускаются логические ошибки, например когда учитываются произведения вида a[i]*a[i] или пары считаются дважды

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

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

0 балловЗадание выполнено неверно.

Это задание решали 3 тыс. раз. С ним справились 15% пользователей.

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

Умение создавать собственные программы (20–40 строк) для анализа числовых последовательностей

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

Тренировочный вариант ЕГЭ по информатике

Задание#T8658

Описание входных и выходных данных

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

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

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