DjangoBB LoFi version

Полная версия: Задача: 1196. Экзамен по истории

Начало » Python для новичков » Задача: 1196. Экзамен по истории

1 2

Vigi

Окт. 27, 2015 12:32:04

Ограничение времени: 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 КБ

подскажите идею…

ZerG

Окт. 27, 2015 13:11:29

sum

Vigi

Окт. 27, 2015 14:23:59

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))

если так ? то снова превышение времени…

Rodegast

Окт. 27, 2015 15:45:55

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

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

Vigi

Окт. 27, 2015 17:27:57

>>> N = [1054, 1492]
>>> M = [1492, 65536, 1492, 100]
>>> len(filter(lambda x: x in N, M))
Traceback (most recent call last):
  File "<input>", line 1, in <module>
TypeError: object of type 'filter' has no len()

Kon52

Окт. 27, 2015 18:29:48

Vigi

У Вас 3ий?
Вам filter() возвращает итератор.
Оберните в list.

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

Kon52

Окт. 27, 2015 20:54:38

len([i for i in M if N.count(i)])

py.user.next

Окт. 28, 2015 01:04:23

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

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

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

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

Vigi

Окт. 28, 2015 04:29:21

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))))

out:

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

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

да ссори не заметил

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

а можно по подробней как реализовать ?

Vigi

Окт. 28, 2015 07:52:34

def binary_search(li, x):
    i = 0
    j = len(li) - 1
    while i < j:
        m = int((i + j) / 2)
        if x > li[m]:
            i = m + 1
        else:
            j = m
    if li[j] ==x:
        return j
    else:
        return None
ch = [int(input()) for _ in range(int(input()))]
st = [int(input()) for e in range(int(input()))]
c = []
for i in st:
    if binary_search(ch, i) != None:
        c.append(1)
print(sum(c))

6538262	10:48:39
28 окт 2015	Vigi	1196. Экзамен по истории	Python 3.4	Time limit exceeded	8	1.513	16 248 КБ

то же не то….

я бы давно уже все бросил но тут сказали, что на питоне это слишком трудно сделать почти не возможно

За державу обидно как-то стало…