Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Задача на Питоне

Альберт Эйнштейн Знаток (447), закрыт 3 года назад
Вот такая задача:

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

Описание входных и выходных данных:
В первой строке входных данных задаётся количество чисел (6<=N<=1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000

Пример входных данных:
8
2
6
5
4
6
7
9
8

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

Пояснение. Из восьми чисел можно составить три пары, удовлетворяющие условию. Для заданного набора чисел получаем пары (2,9) (2,8) (6,8). Разности чисел в этих парах равны 7,6,2. Одна из этих разностей кратна 3

МОЕ РЕШЕНИЕ:
c = 3
n = int(input())
a = [0] * n
k = 0
for i in range(n):
a[i] = int(input())
for i in range(n):
for j in range(i+6, n):
if (a[i] - a[j]) % c == 0:
k+=1
print(k)

ВРОДЕ ПРАВИЛЬНЫЙ ОТВЕТ ВЫДАЕТ, НО ВЕРНО ЛИ, ПОМОГИТЕ РАЗОБРАТЬСЯ, СПАСИБКИ)
Лучший ответ
user49912 Оракул (51192) 3 года назад
да, всё верно
Альберт ЭйнштейнЗнаток (447) 3 года назад
она эффективна, бро? сдаю просто егэ в июле
user49912 Оракул (51192) приведённое решение работает за O(n^2) я уверен, что у этой задачи существует решение как минимум за O(n log n), так что в абсолютных цифрах твоё решение не является эффективным, но для n<=1000 обычного двойного цикла вполне достаточно
Альберт ЭйнштейнЗнаток (447) 3 года назад
любой комментарий мне поможет
Остальные ответы
Похожие вопросы