DjangoBB LoFi version

Полная версия: Плохая реализация задачи "Забастовки"

Начало » Python для новичков » Плохая реализация задачи "Забастовки"

DryFruit

Июль 7, 2017 00:35:39

Добрый день.
В общем намалевал я тут кое-что, вроде как правильно, ибо тесты проходят, по следующей задаче:
"Условие
Политическая жизнь одной страны очень оживленная. В стране действует K политических партий, каждая из которых регулярно объявляет национальную забастовку. Дни, когда хотя бы одна из партий объявляет забастовку, при условии, что это не суббота или воскресенье (когда и так никто не работает), наносят большой ущерб экономике страны.
i-я партия объявляет забастовки строго каждые b_i дней, начиная с дня с номером a_i. То есть i-я партия объявляет забастовки в дни a_i, a_i + b_i, a_i + 2 * b_i и т.д. Если в какой-то день несколько партий объявляет забастовку, то это считается одной общенациональной забастовкой.
В календаре страны N дней, пронумерованных, начиная с единицы. Первый день года является понедельником, шестой и седьмой дни года — выходные, неделя состоит из семи дней.
В первой строке даны числа N и K. Далее идет K строк, описывающие графики проведения забастовок. i-я строка содержит числа a_i и b_i. Вам нужно определить число забастовок, произошедших в этой стране в течении года.“

Я думаю тут ни раз всплывало это задание, но мне интересно как можно оптимизировать именно мой ”тяп-ляп" код.

 nk, res, output = [int(item) for item in input().split()], set(), set()
#Поиск забастовок по шаблону  партий
def find_riot(month_day_quantity, start_day, step_day, weekend):
    ret = set()
    for day in range(1,month_day_quantity +1):
        if ((day - start_day > 0 and (day - start_day)%step_day == 0) or day == start_day) and day not in weekend:
            ret.add(day)
    return ret
#Поиск выходных 6 и 7 дней недели
for i in range(1,(nk[0]//7)+1):
    res.add((i*7)-1)
    res.add(i*7)
if (nk[0] % 7) % 6 == 0:
    res.add(nk[0]-1)
for i in range(nk[1]):
    st = [int(item) for item in input().split()]
    output |= find_riot(nk[0],st[0],st[1],res)
print(len(output))#,output, res, sep='\n')

Входные данные для примера:
19 3
2 3
3 5
9 8

DryFruit

Июль 7, 2017 12:11:09

Оптимизировал “поиск дней забостовок”:

 nk, res, output = [int(item) for item in input().split()], set(), set()
#Поиск забастовок по шаблону  партий
def find_riot(month_day_quantity, start_day, step_day, weekend):
    ret = set()
    for day in range(((month_day_quantity - start_day) // step_day)+1):
        if (day * step_day) + start_day not in weekend:
            ret.add((day * step_day) + start_day)
    return ret
#Поиск выходных 6 и 7 дней недели
for i in range(1,(nk[0] // 7) + 1):
    res.add((i * 7) - 1)
    res.add(i * 7)
if (nk[0] % 7) % 6 == 0:
    res.add(nk[0] - 1)
for i in range(nk[1]):
    st = [int(item) for item in input().split()]
    output |= find_riot(nk[0], st[0], st[1], res)
print(len(output))

Но все равно выполняется долго при расчете на 100 000 дней.

У меня закрадывается подозрение, что данную задачу можно решить в 2-3 строки.

marvellik

Июль 7, 2017 12:56:10

DryFruit
У меня закрадывается подозрение, что данную задачу можно решить в 2-3 строки

ну не совсем в 2-3 строки. у меня в 11 вышло а вот решение разработчиков(с сайта питонтьютор )

 N, K = [int(s) for s in input().split()]
work_days = set([day for day in range(1, N + 1) if day % 7 not in (6, 0)])
no_strikes = set(work_days)
for party in range(K):
    a, b = [int(s) for s in input().split()]
    max_strikes = (N - a) // b + 1
    no_strikes -= {a + b*i for i in range(max_strikes)}
print(len(work_days) - len(no_strikes))

DryFruit

Июль 7, 2017 14:19:51

Эмм но вот во 2 строке:

 work_days = set([day for day in range(1, N + 1) if day % 7 not in (6, 0)])

Получается, что если у меня 1 000 000 дней я буду прокатывать 1 000 000 циклов вместо заранее известных 142 857 цикла. Это же не оптимизация, а лаконичность в ущерб быстродействию.

foreinger

Сен. 12, 2018 14:02:11

 n,k=[int(i) for i in input().split()]
weekends=set(range(6,n+1,7))
weekends.update(set(range(7,n+1,7)))
strike=set()
for i in range(k):
    a,b=[int(j) for j in input().split()]
    A=set(range(a,n+1,b))
    strike.update(A)
strike-=weekends
print(len(strike))

меня получился такой вариант, с минимальным использованием циклов