Укажите использованный язык программирования и его версию.
Условие
Дан набор из N целых положительных чисел. Из этих чисел формируются все возможные пары (парой считаются два элемента, которые находятся на разных местах в наборе, порядок чисел в паре не учитывается), в каждой паре вычисляется сумма элементов. Необходимо определить количество пар, для которых полученная сумма делится на 8.Напишите эффективную по времени и по памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает одного килобайта и не увеличивается с ростом N.Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, — 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Описание входных и выходных данныхВ первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.Пример входных данных:5157111 Пример выходных данных для приведённого выше примера входных данных:3Из 5 чисел можно составить 10 пар. В данном случае у трёх пар сумма делится на 8: 1 + 7, 1 + 7 (в наборе две единицы, поэтому пару 1 + 7 можно составить двумя способами), 5 + 11.
Формат задания
Решение по шагам
Как рассуждать
Решение. Чтобы сумма двух чисел делилась на 8, они оба должны делиться на 8 либо сумма их остатков от деления на 8 должна быть равна 8.Разобьём все числа исходного набора на 8 групп по значению остатка от деления на 8 и подсчитаем количество чисел в каждой группе. Сами числа можно не хранить, достаточно при вводе определить остаток от деления очередного числа на 8 и увеличить соответствующий счётчик. Таким образом, независимо от количества чисел в исходном наборе после чтения исходных данных для хранения необходимой информации хватит массива из 8 элементов, и программа получится эффективной по памяти.
Зная количество элементов для каждого остатка, можно определить количество подходящих пар. Для чисел с остатками 0 (числа, кратные
Осталось ещё 3 шага
и 4 оба числа в паре должны быть в одной и…
/ 2)else: s2 = 0if a[0] >= 2: s3 =…
/ 2)else: s3 = 0print(s1 + s2 + s3)…
Бесплатно · займёт минуту