Решение номера 8730 ФИПИ

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3 (разница в индексах элементов пары должна быть 3 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 23.

 

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

В первой строке входных данных задаётся количество чисел N (3 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.

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

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

6

46

2

3

5

4

23

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

5

Пояснение. Из шести заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 46·5, 46·4, 46·23, 2·4, 2·23, 3·23. Из них на 23 делятся 5 произведений.

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

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

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

 

Объяснение

Так как число 23 – простое, значит нам достаточно хотя бы одного числа кратного 13, чтобы составить произведение кратное 23. В массиве будем смотреть на номер элемента, полученный путем вычисления остатка от порядка элемента и 3. Если этот элемент делится на 23, то в переменную count прибавляем единицу. При вводе очередного значения мы будем рассматривать его как потенциальную пару с элементом на 3 места ранее (с элементом который рассматриваем в массиве). Если очередное значение делится на 23, то прибавляем к ответу количество чисел без ближайших трех. Иначе прибавляем к ответу количество элементов делящихся на 23.

 

Решение на языке Паскаль

Показать решение

 

Решение на языке Python

Показать решение

 

Похожие задачи: 8703; 8757

 

Оставить комментарий