DjangoBB LoFi version

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

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

1 2

py.user.next

Окт. 28, 2015 07:55:50

>>> import bisect
>>> 
>>> def bsearch(lst, x):
...     return lst[bisect.bisect(lst, x) - 1] == x
... 
>>> bsearch([1, 2, 3], 1)
True
>>> bsearch([1, 2, 3], 2)
True
>>> bsearch([1, 2, 3], 3)
True
>>> bsearch([1, 2, 3], 0)
False
>>> bsearch([1, 2, 3], 4)
False
>>>

У препода в списке может быть 15000 чисел, а у студента - 1000000. Если у студента весь список состоит из одного числа, то нет смысла искать его в преподском после первого совпадения или несовпадения. Поэтому нужно дополнительное множество (нагруженное (словарь по-питоновски)), которое будет хранить проверенные числа. А чтобы память не росла, числа из студенческого списка нужно извлекать.

Vigi

Окт. 29, 2015 06:07:28

import bisect
def bin_search(lst, x):
    return lst[bisect.bisect(lst, x) - 1] == x
tch = sorted({int(input()) for _ in range(int(input()))})
std = sorted([int(input()) for _ in range(int(input()))])
r = []
for i in [i for i in std if tch[0] <= i <= tch[-1]]:
    if bin_search(tch, i):
        r.append(1)
print(len(r))

6540441	09:05:39
29 окт 2015	Vigi	1196. Экзамен по истории	Python 3.4	Time limit exceeded	8	1.528	16 260 КБ

вот, что не так…?

Vigi

Окт. 30, 2015 05:00:50

n = int(input())
tch = [int(input()) for _ in range(n)]
m = int(input())
std = sorted([int(input()) for w in range(m)])
 
i = j = r = 0
while True:
    if i == n:
        break
    if j == m:
        break
 
    if tch[i] == std[j]:
        r += 1
        j += 1
    elif tch[i] < std[j]:
        i += 1
    elif tch[i] > std[j]:
        j += 1
 
print(r)

пришел к вот такому коду, но опять лимит превышен. Хотя этот же алгоритм на c++ работает и проходит временное ограничение. Нужно оптимизировать создание списка учителя и студента…. наверное…
Вариант возможен ??? в питоне вроде в место input можно не помни точно cin!? использовать… \
Что скажете..

py.user.next

Окт. 30, 2015 06:48:21

Vigi
в питоне вроде в место input можно не помни точно cin!? использовать

Там он не реальное время показывает. Похоже, он там выбирает только суть алгоритма, для неё замеряет какое-то время, делает вывод об алгоритме, а потом уже для вывода формирует какое-то время, немного превышающее.
Поэтому не факт, что ввод влияет на его замеры.

Vigi

Окт. 30, 2015 10:02:24

знать бы точно

по рейтингу эту задачу успешно на 2_м питоне cделали 20 человек на 3_м 13 вопрос как?

Рейтинг решений задачи Экзамен по истории
Все языки (5918) | C/C++ (3519) | Pascal (1870) | Java (430) | C#/VB (156) | Go (5) | Python2 (20) | Python3 (13) | Ruby (4) | Haskell (3) | Scala (4)

py.user.next

Окт. 30, 2015 11:55:58

Думаешь, стоит попробовать её решить, чтобы сайт её принял?

py.user.next

Окт. 31, 2015 06:39:36

Вот этот прошёл.

#!/usr/bin/env python3
 
import sys
 
def f():
    prep = set()
    pn = int(input())
    while pn > 0:
        prep.add(input())
        pn -= 1
    input()
    n = 0
    for i in map(str.rstrip, sys.stdin):
        if i in prep:
            n += 1
    print(n)
 
f()

Привел немного.

#!/usr/bin/env python3
 
import sys
 
def f():
    prep = set(input() for _ in range(int(input())))
    input()
    print(sum(i in prep for i in map(str.rstrip, sys.stdin)))
 
f()

Vigi

Окт. 31, 2015 09:28:30

Ну круто сенькс