Помогите решить задачу по Python
H. Таинство суммы
0
Имя входного файла
стандартный ввод
Имя выходного файла
стандартный вывод
Ограничение по времени
1 секунда
Ограничение по памяти
64 мегабайта
— Брат мой, Магистр Ордена хочет узнать завтра о результатах наших многолетних изысканий. Он хочет видеть, ни много, ни мало, Суммирующую Машину! Даже более того: он хочет, чтобы наша Машина — всего лишь машина — продемонстрировала свое постижение Таинства Суммы настолько глубоко, насколько это возможно. Он хочет, чтобы Машина нашла каких-нибудь два числа, дающих в сумме священное число 10000!
— Тс-с-с! Но это же безумство, граничащее с кощунством! Как Машина может вычислить священное число? Двадцать семь лет мы работаем над ней, и смогли только лишь научить ее отвечать на вопрос: «Больше сумма двух введенных чисел, чем 10000, или меньше?». Но разве может смертный найти два таких числа, чтобы их сумма оказалась равна 10000?
— И все же нам придется сделать это с помощью нашей Машины, пусть она и неспособна на это. Иначе у нас будут... ну, скажем так, крупные неприятности, если кипящее масло можно назвать таким словом. Впрочем, у меня есть идея. Помнишь, на той неделе мы ввели в Машину числа -7 и 13, она ответила, что их Сумма меньше 10000. Я не знаю, как это проверить, но нам ничего не остается, как доверять созданию наших рук. Что, если теперь мы возьмем число большее, чем -7 и снова запустим Машину? И будем так делать снова и снова, пока не найдем такое число, которое в сумме с 13 даст 10000! Надо только подготовить список возрастающих чисел.
— Не верю я в эту идею... Давай лучше начнем с суммы, заведомо большей, чем Священное число и будем уменьшать одно из слагаемых, так у нас больше шансов избегнуть кипяще... крупных неприятностей.
Так ни о чём и не договорившись, Братья разошлись по своим кельям. К следующему дню, каждый из них подготовил такой список чисел, который, по его мнению, мог бы их спасти... Смогут ли спасти их оба списка вместе?
Ваша программа должна определять, можно ли из двух списков целых чисел выбрать по одному числу так, чтобы в сумме они составили 10000.
Формат входных данных
Входные данные состоят из двух списков — одного, потом другого. Формат каждого из этих списков таков: в первой строчке записано количество Ni чисел в i-м списке, далее в Ni строчках по одному числу в строке записаны сами списки. Выполняются неравенства 1≤Ni≤100000, все элементы списков лежат в диапазоне от −106 до 106 включительно. Первый список упорядочен по возрастанию, второй — по убыванию.
Формат выходных данных
На выходе следует записать «YES», если из списков можно выбрать по числу, которые в сумме дадут 10000 и «NO» в противном случае.
Примеры
входные данные
4
-175
18
19
10424
3
8951
-424
-788
выходные данные
YES
Вот еще вариант.
Лишнее уберите сами.
--------------------------------------------------------
from timeit import default_timer as timer
from random import randint
"""
# Закомментирован участок
# для создания двух файлов с наборами чисел
A = []
for i in range(100_000):
~~~~A.append(randint(-1000_000, 1000_000))
A.sort()
with open('file1.txt','w') as f:
~~~~for a in A:
~~~~~~~~f.write(str(a)+'\n')
A = []
for i in range(100_000):
~~~~A.append(randint(-1000_000, 1000_000))
A.sort(reverse=True)
with open('file2.txt','w') as f:
~~~~for a in A:
~~~~~~~~f.write(str(a)+'\n')
"""
res = 'NO'
with open('file1.txt') as f:
~~~~A1 = list(map(int, f.read().rstrip().split('\n')))
with open('file2.txt') as f:
~~~~A2 = list(map(int, f.read().rstrip().split('\n')))
start = timer()
#---------------
X = 10_000
for a in A2:
~~~~mid = len(A1)//2
~~~~left = -1
~~~~right = len(A1)
~~~~while left < right-1:
~~~~~~~~mid = (left+right)//2
~~~~~~~~if a + A1[mid] > X:
~~~~~~~~~~~~right=mid
~~~~~~~~else:
~~~~~~~~~~~~left=mid
~~~~if left>=0 and a+A1[left]==X:
~~~~~~~~print(A1[left], '+', a, '=', A1[left]+ a)
~~~~~~~~res = "YES"
~~~~~~~~break
~~~~~~~~
print(res)
#---------------
end = timer()
print(end - start)
res = 'No'
l1, l2 = [], []
n1 = int(input())
while len(l1) < n1:
~~~~a = int(input())
~~~~~~~~l1.append(a)
n2 = int(input())
while len(l2) < n2:
~~~~a = int(input())
~~~~~~~~l2.append(a)
if any((x == 10000 for x in [i + j for i in l1 for j in l2])): res = 'Yes'
print(res)
# списки при вводе неупорядочены
# если потребуется, перед добавлением в список l.append(a) можно проверять <> ли число последнего в списке if a <> l[-1]
Tl;dr