Python-сообщество

Ограничение времени: 1.5 секунды
Ограничение памяти: 64 МБ
Будем справедливы: сессия ставит задачи не только студентам, но и преподавателям. Любой преподаватель обучает немалое количество студентов, а ведь каждого надо еще и проверить. Поэтому один из преподавателей решил принимать экзамен по истории по такой упрощённой процедуре: студент записывает все известные ему «исторические» даты (достаточно, чтобы он написал только года, но, конечно, мог объяснить, чем замечательна та или иная дата). Преподаватель же держит перед глазами список дат, которые студент должен знать. Для оценки знаний студента преподаватель подсчитывает количество чисел в списке студента, которые также есть в списке преподавателя. В зависимости от полученного числа и выставляется итоговая оценка.
Вы должны оказать посильную помощь в автоматизации этого процесса, разработав программу для подсчёта количества совпадений в списках студента и преподавателя.
Исходные данные
В первой строке содержится число N — количество записей в списке преподавателя. 1 ≤ N ≤ 15000. Затем идет N строк, содержащих список преподавателя, по одной дате в строке. Записаны только года. Каждый год — целое число в пределах от 1 до 10^9. Даты в этом списке отсортированы по неубыванию. В следующей после списка строке содержится число M — количество записей в списке студента, 1 ≤ M ≤ 10 ^6. Затем также M строк с датами (записаны только года, каждый год — целое число в пределах от 1 до 10^9). Этот список не отсортирован. В списке как студента, так и преподавателя даты могут повторяться.
Результат
Вы должны вывести одно число — количество чисел во втором списке, которые также содержатся в первом.
Пример
исходные данные:
2
1054
1492
4
1492
65536
1492
100

результат:
2

Парюсь весь день, не могу оптимизировать

c = 0
teach_list = set(([int(input()) for _ in range(int(input()))]))
for i in range(int(input())):
    if int(input()) in teach_list:
        c += 1
print(c)

6535587	13:35:02
27 окт 2015	Vigi	1196. Экзамен по истории	Python 3.4	Time limit exceeded	8	1.528	640 КБ

Отредактировано Vigi (Окт. 28, 2015 04:18:36)

sum

ZerG
sum

t = []
teach_list = set(([int(input()) for _ in range(int(input()))]))
for i in range(int(input())):
    if int(input()) in teach_list:
        t.append(1)
print(sum(t))

Отредактировано Vigi (Окт. 27, 2015 14:25:02)

> снова превышение времени…
Ты что хочешь сказать что эта детская задача более полутора секунд работает? Не верю!

>>> N = [1054, 1492]
>>> M = [1492, 65536, 1492, 100]
>>> len(filter(lambda x: x in N, M))
2

Vigi

>>> N = [1, 2]
>>> M = [2, 3, 2, 4]
>>> len(list(filter(lambda x: x in N, M)))
2
>>>

Отредактировано Kon52 (Окт. 27, 2015 18:30:19)

Rodegast
Ты что хочешь сказать что эта детская задача более полутора секунд работает? Не верю!

Vigi
Каждый год — целое число в пределах от 1 до 109.

Kon52

ch = [int(input()) for _ in range(int(input()))]
sd = [int(input()) for _ in range(int(input()))]
print(len(list(filter(lambda x: x in ch, sd))))

6537990	07:20:59
28 окт 2015	Vigi	1196. Экзамен по истории	Python 3.4	Time limit exceeded	8	1.544	16 268 КБ

Он её ещё и скопировал неправильно. Степени превратились в обычные цифры.

Скорее всего, надо применять бинарный поиск, так как преподские даты отсортированы.