08 Макс/мин, кол-во пар, сумма/разность/произведение кратно/не кратно на расстоянии
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности, в которых между любыми двумя элементами расстояние не менее 45 (расстояние – разность порядковых номеров). Необходимо определить максимальную сумму элементов пары, кратную 1234.
Входные данные: Даны два входных файла, каждый из которых содержит в первой строке количество пар N
. Каждая из следующих N строк содержит одно натуральное число.
Переборное решение:
f = open(’A.txt’) n = int(f.readline()) a = [int(i) for i in f] ans = -10 ** 10 k = 1234 # Чему должна быть кратна сумма s = 45 # Расстояние между элементами for i in range(n): for j in range(i + 1, n): if (a[i] + a[j]) % k == 0 and j - i >= s: ans = max(ans, a[i] + a[j]) print(ans)
Эффективное решение:
f = open(’B.txt’) n = int(f.readline()) a = [int(i) for i in f] ans = -10 ** 10 k = 1234 # Чему должна быть кратна сумма s = 45 # Расстояние между элементами # Список максимальных чисел с определенными остатками от деления на k # Например, под индексом 3 хранится максимальное число с остатком 3 nums = [-10 ** 10] * k for i in range(s, n): # Считаем остаток от деления первого числа пары на k ost1 = a[i - s] % k # Обновляем максимум по остатку nums[ost1] = max(nums[ost1], a[i - s]) # Считаем остаток, который должен быть у числа, # которое можно поставить в пару с текущим ost2 = (k - (a[i] % k)) % k # Обновляем ответ, если он больше предыдущего ans = max(ans, a[i] + nums[ost2]) print(ans)
Ошибка.
Попробуйте повторить позже
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности, в которых между любыми двумя элементами расстояние не менее 38 (расстояние – разность порядковых номеров). Необходимо определить максимальную разность элементов пары, кратную 456 (под разностью понимать вычитание из элемента, находящегося позже в последовательности, того элемента, который встречается раньше в последовательности).
Входные данные: Даны два входных файла, каждый из которых содержит в первой строке количество пар N
. Каждая из следующих N строк содержит одно натуральное число.
Переборное решение:
f = open(’A.txt’) n = int(f.readline()) a = [int(i) for i in f] ans = -10 ** 10 k = 456 # Чему должна быть кратна сумма s = 38 # Расстояние между элементами for i in range(n): for j in range(i + 1, n): if (a[j] - a[i]) % k == 0 and j - i >= s: ans = max(ans, a[j] - a[i]) print(ans)
Эффективное решение:
f = open(’2_27B_pairs.txt’) n = int(f.readline()) a = [int(i) for i in f] d = 38 k = 456 # Список из минимальных чисел с определенным остатком от деления t = [10 ** 10] * k mx = -1 for i in range(d, len(a)): # Обрабатываем элемент на расстоянии d от текущего ost1 = a[i - d] % k # Если он меньше прошлого с таким остатком - обновляем список t[ost1] = min(t[ost1], a[i - d]) # Вычисляем остаток для пары нашего числа ost2 = a[i] % k # Если уже нашлось число с таким остатком - считаем разность и обновляем максимум if t[ost2] < 10 ** 10: rz = a[i] - t[ost2] if rz > mx: mx = rz print(mx)
Ошибка.
Попробуйте повторить позже
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности, в которых между любыми двумя элементами расстояние не менее 67 (расстояние – разность порядковых номеров). Необходимо определить максимальную разность элементов пары, кратную 876 (под разностью понимать любую положительную разность между любыми двумя подходящими под условие элементами последовательности).
Входные данные: Даны два входных файла, каждый из которых содержит в первой строке количество пар N
. Каждая из следующих N строк содержит одно натуральное число.
Переборное решение:
f = open(’A.txt’) n = int(f.readline()) a = [int(i) for i in f] ans = -10 ** 10 k = 876 # Чему должна быть кратна сумма s = 67 # Расстояние между элементами for i in range(n): for j in range(i + 1, n): if abs((a[j] - a[i])) % k == 0 and j - i >= s: ans = max(ans, abs(a[j] - a[i])) print(ans)
Эффективное решение:
f = open(’3_27B_pairs.txt’) n = int(f.readline()) a = [int(i) for i in f] d = 67 k = 876 # Список из минимальных чисел с определенным остатком от деления tmn = [10 ** 10] * k # Список из максимальных чисел с определенным остатком от деления tmx = [-1] * k mx = -1 for i in range(d, len(a)): # Обрабатываем элемент на расстоянии d от текущего ost1 = a[i - d] % k # Если он меньше прошлого с таким остатком - обновляем список минимумов tmn[ost1] = min(tmn[ost1], a[i - d]) # Если он больше прошлого с таким остатком - обновляем список максимумов tmx[ost1] = max(tmx[ost1], a[i - d]) # Вычисляем остаток для пары нашего числа ost2 = a[i] % k # Если уже нашлось минимальное число с таким остатком - считаем разность и обновляем максимум if tmn[ost2] < 10 ** 10: rz = a[i] - tmn[ost2] if rz > mx: mx = rz # Если уже нашлось максимальное число с таким остатком - считаем разность и обновляем максимум if tmx[ost2] > -1: rz = tmx[ost2] - a[i] if rz > mx: mx = rz print(mx)
Ошибка.
Попробуйте повторить позже
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности, в которых между любыми двумя элементами расстояние не менее 100 (расстояние – разность порядковых номеров). Необходимо определить минимальную сумму элементов пары, кратную 5693.
Входные данные: Даны два входных файла, каждый из которых содержит в первой строке количество пар N
. Каждая из следующих N строк содержит одно натуральное число.
Переборное решение:
f = open(’A.txt’) n = int(f.readline()) a = [int(i) for i in f] ans = 10 ** 10 k = 5693 # Чему должна быть кратна сумма s = 100 # Расстояние между элементами for i in range(n): for j in range(i + 1, n): if (a[i] + a[j]) % k == 0 and j - i >= s: ans = min(ans, a[i] + a[j]) print(ans)
Эффективное решение:
f = open(’4_27A_pairs.txt’) n = int(f.readline()) a = [int(i) for i in f] d = 100 k = 5693 # Список из минимальных чисел с определенным остатком от деления t = [10 ** 10] * k mn = 10 ** 10 for i in range(d, len(a)): # Обрабатываем элемент на расстоянии d от текущего ost1 = a[i - d] % k # Если он меньше прошлого с таким остатком - обновляем список t[ost1] = min(t[ost1], a[i - d]) # Вычисляем остаток для пары нашего числа ost2 = (k - (a[i] % k)) % k # Если уже нашлось число с таким остатком - считаем и обновляем минимум if t[ost2] < 10 ** 10: sm = a[i] + t[ost2] if sm < mn: mn = sm print(mn)
Ошибка.
Попробуйте повторить позже
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности, в которых между любыми двумя элементами расстояние не более 28 (расстояние – разность порядковых номеров). Необходимо определить максимальную сумму элементов пары, кратную 777.
Входные данные: Даны два входных файла, каждый из которых содержит в первой строке количество пар N
. Каждая из следующих N строк содержит одно натуральное число.
Переборное решение:
f = open(’A.txt’) n = int(f.readline()) a = [int(i) for i in f] ans = -10 ** 10 k = 777 # Чему должна быть кратна сумма s = 28 # Расстояние между элементами for i in range(n): for j in range(i + 1, n): if (a[j] + a[i]) % k == 0 and j - i <= s: ans = max(ans, a[i] + a[j]) print(ans)
Эффективное решение:
f = open(’5_27B_pairs.txt’) n = int(f.readline()) a = [int(i) for i in f] d = 28 k = 777 # Список из элементов на нужном расстоянии lst = [] mx = -1 for i in range(len(a)): # Считываем текущий элемент a1 = a[i] # Проходимся по d элементов до текущего for a2 in lst: # Если сумма удовлетворяет условию - обновляем максимум if (a1 + a2) % k == 0: mx = max(mx, a1 + a2) # Добавляем текущий элемент в массив lst.append(a1) # Убираем элемент, который будет слишком далеко для нового элемента if len(lst) > d: lst.pop(0) print(mx)
Ошибка.
Попробуйте повторить позже
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности, в которых между любыми двумя элементами расстояние не более 59 (расстояние – разность порядковых номеров). Необходимо определить минимальную кратную 689 сумму элементов пары, имеющих одинаковые первые две цифры.
Входные данные: Даны два входных файла, каждый из которых содержит в первой строке количество пар N
. Каждая из следующих N строк содержит одно натуральное число.
Переборное решение:
f = open(’A.txt’) n = int(f.readline()) a = [int(i) for i in f] ans = 10 ** 10 k = 689 # Чему должна быть кратна сумма s = 59 # Расстояние между элементами for i in range(n): for j in range(i + 1, n): if (a[j] + a[i]) % k == 0 and j - i <= s and str(a[i])[:2] == str(a[j])[:2]: ans = min(ans, a[i] + a[j]) print(ans)
Эффективное решение:
f = open(’6_27A_pairs.txt’) n = int(f.readline()) a = [int(i) for i in f] d = 59 k = 689 # Список из элементов на нужном расстоянии lst = [] mn = 10 ** 10 for i in range(len(a)): # Считываем текущий элемент a1 = a[i] # Проходимся по d элементов до текущего for a2 in lst: # Если сумма удовлетворяет условию - обновляем минимум if (a1 + a2) % k == 0 and str(a1)[:2] == str(a2)[:2]: mn = min(mn, a1 + a2) # Добавляем текущий элемент в массив lst.append(a1) # Убираем элемент, который будет слишком далеко для нового элемента if len(lst) > d: lst.pop(0) print(mn)
Ошибка.
Попробуйте повторить позже
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности, в которых между любыми двумя элементами расстояние не менее 70 (расстояние – разность порядковых номеров). Необходимо определить максимальную сумму кратную 7654 элементов пары, имеющих одинаковые остатки от деления на 3.
Входные данные: Даны два входных файла, каждый из которых содержит в первой строке количество пар N
. Каждая из следующих N строк содержит одно натуральное число.
Переборное решение:
f = open(’A.txt’) n = int(f.readline()) a = [int(i) for i in f] ans = -10 ** 10 k = 7654 # Чему должна быть кратна сумма s = 70 # Расстояние между элементами for i in range(n): for j in range(i + 1, n): if (a[i] + a[j]) % k == 0 and a[i] % 3 == a[j] % 3 and j - i >= s: ans = max(ans, a[i] + a[j]) print(ans)
Эффективное решение:
f = open(’7_27A_pairs.txt’) n = int(f.readline()) a = [int(i) for i in f] d = 70 k = 7654 r = 3 # Список из максимальных чисел с определенным остатком от деления t = [[-1] * k for i in range(r)] mx = -1 for i in range(d, len(a)): # Обрабатываем элемент на расстоянии d от текущего ost1 = a[i - d] % k ost1_1 = a[i - d] % r # Если он больше прошлого с таким остатком - обновляем список t[ost1_1][ost1] = max(t[ost1_1][ost1], a[i - d]) # Вычисляем остаток для пары нашего числа ost2 = (k - (a[i] % k)) % k ost2_1 = a[i] % r # Если уже нашлось число с таким остатком - считаем и обновляем минимум if t[ost2_1][ost2] > -1: sm = a[i] + t[ost2_1][ost2] if sm > mx: mx = sm print(mx)
Ошибка.
Попробуйте повторить позже
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются тройки различных элементов последовательности, в которых между любыми двумя элементами расстояние не менее 35 (расстояние – разность порядковых номеров). Необходимо определить максимальную сумму такой тройки, кратную 937.
Входные данные: Даны два входных файла, каждый из которых содержит в первой строке количество пар N
. Каждая из следующих N строк содержит одно натуральное число.
Переборное решение:
f = open(’A.txt’) n = int(f.readline()) a = [int(i) for i in f] ans = 0 k = 937 # Чему должна быть кратна сумма s = 35 # Расстояние между элементами for i in range(n): for j in range(i + 1, n): for r in range(j + 1, n): if j - i >= s and r - j >= s and (a[i] + a[j] + a[r]) % k == 0: ans = max(ans, a[i] + a[j] + a[r]) print(ans)
Эффективное решение:
f = open(’8_27A_pairs.txt’) n = int(f.readline()) a = [int(i) for i in f] d = 35 k = 937 # Список из максимальных чисел с определенным остатком от деления t = [-1] * k # Список из пар с максимальными суммами c определенным остатком v = [[-1, -1] for i in range(k)] mx = -1 for i in range(d * 2, len(a)): # Обрабатываем элемент на расстоянии 2*d от текущего ost1 = a[i - d * 2] % k # Если он больше прошлого с таким остатком - обновляем список t[ost1] = max(t[ost1], a[i - d * 2]) # Обрабатываем средний элемент - на расстоянии d от текущего ost2 = a[i - d] % k # Для каждого из максимальных первых элементов (для каждого остатка) # создаём новые суммы с новым средним элементом и обновляем # эти суммы в списке v, если они получились больше прошлых for j in range(k): if t[j] > -1: sm_pair = t[j] + a[i - d] if sm_pair > sum(v[(j + ost2) % k]): v[(j + ost2) % k] = [t[j], a[i - d]] # Вычисляем остаток для пары в сумму к нашему числу ost3 = (k - (a[i] % k)) % k # Если уже нашлось число с таким остатком - считаем и обновляем максимум if sum(v[ost3]) > -1: sm = a[i] + sum(v[ost3]) if sm > mx: mx = sm print(mx)
Ошибка.
Попробуйте повторить позже
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются тройки различных элементов последовательности, в которых между любыми двумя элементами расстояние не менее 85 (расстояние – разность порядковых номеров). Необходимо определить минимальную сумму такой тройки, кратную 555.
Входные данные: Даны два входных файла, каждый из которых содержит в первой строке количество пар N
. Каждая из следующих N строк содержит одно натуральное число.
f = open(’9_27A_pairs.txt’) n = int(f.readline()) a = [int(i) for i in f] d = 85 k = 555 # Список из минимальных чисел с определенным остатком от деления t = [10 ** 10] * k # Список из пар с минимальными суммами c определенным остатком v = [[10 ** 10, 10 ** 10] for i in range(k)] mn = 10 ** 10 for i in range(d * 2, len(a)): # Обрабатываем элемент на расстоянии 2*d от текущего ost1 = a[i - d * 2] % k # Если он больше прошлого с таким остатком - обновляем список t[ost1] = min(t[ost1], a[i - d * 2]) # Обрабатываем средний элемент - на расстоянии d от текущего ost2 = a[i - d] % k # Для каждого из максимальных первых элементов (для каждого остатка) # создаём новые суммы с новым средним элементом и обновляем # эти суммы в списке v, если они получились больше прошлых for j in range(k): if t[j] < 10 ** 10: sm_pair = t[j] + a[i - d] if sm_pair < sum(v[(j + ost2) % k]): v[(j + ost2) % k] = [t[j], a[i - d]] # Вычисляем остаток для пары в сумму к нашему числу ost3 = (k - (a[i] % k)) % k # Если уже нашлось число с таким остатком - считаем и обновляем максимум if sum(v[ost3]) < 10 ** 10: sm = a[i] + sum(v[ost3]) if sm < mn: mn = sm print(mn)
Ошибка.
Попробуйте повторить позже
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются тройки различных элементов последовательности, в которых между любыми двумя элементами расстояние не менее 99 (расстояние – разность порядковых номеров). Необходимо определить максимальную сумму такой тройки, кратную 123. Причём каждый элемент тройки должен делиться на 3 без остатка.
Входные данные: Даны два входных файла, каждый из которых содержит в первой строке количество пар N
. Каждая из следующих N строк содержит одно натуральное число.
f = open(’10_27B_pairs.txt’) n = int(f.readline()) a = [int(i) for i in f] d = 99 k = 123 # Список из максимальных чисел с определенным остатком от деления t = [-1] * k # Список из пар с максимальными суммами c определенным остатком v = [[-1, -1] for i in range(k)] mx = -1 for i in range(d * 2, len(a)): if a[i - d * 2] % 3 == 0: # Обрабатываем элемент на расстоянии 2*d от текущего ost1 = a[i - d * 2] % k # Если он больше прошлого с таким остатком - обновляем список t[ost1] = max(t[ost1], a[i - d * 2]) if a[i - d] % 3 == 0: # Обрабатываем средний элемент - на расстоянии d от текущего ost2 = a[i - d] % k # Для каждого из максимальных первых элементов (для каждого остатка) # создаём новые суммы с новым средним элементом и обновляем # эти суммы в списке v, если они получились больше прошлых for j in range(k): if t[j] > -1: sm_pair = t[j] + a[i - d] if sm_pair > sum(v[(j + ost2) % k]): v[(j + ost2) % k] = [t[j], a[i - d]] if a[i] % 3 == 0: # Вычисляем остаток для пары в сумму к нашему числу ost3 = (k - (a[i] % k)) % k # Если уже нашлось число с таким остатком - считаем и обновляем максимум if sum(v[ost3]) > -1: sm = a[i] + sum(v[ost3]) if sm > mx: mx = sm print(mx)
