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

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

 

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

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

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

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

6

26

2

3

5

4

13

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

5

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

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

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

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

 

Объяснение

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

 

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

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

 

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

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

 

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

 

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