Вырубка Леса

@Антон255 · Регистрация: 03.08.2018

Студворк — интернет-сервис помощи студентам

Есть такая задача, условие ниже. У меня получилось ее решить, но способом "в лоб". Большинство контестов проходит, но все же есть такие экземпляры ввода, когда статус после компиляции TL. Есть ли какой-то способ явно ускорить работу программы? Возможно, совсем другим алгоритмом. Мое решение с TL после условия.

Фермер Николай нанял двух лесорубов: Дмитрия и Фёдора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут X деревьев.

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т. д.

Фёдор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Фёдор отдыхает в M-й, 2M-й, 3M-й день, и т. д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A+B деревьев, в дни, когда отдыхает только Фёдор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он сможет засеять кукурузное поле.

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Формат входных данных
Программа получает на вход пять целых чисел, разделённых пробелами: A, K, B, M и X (1≤A,B≤10^9, 2≤K,M≤10^18, 1≤X≤10^18).

Формат выходных данных
Программа должна вывести одно целое число — искомое количество дней.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
A, K, B, M, X = map(int, input().split())
dmWork = True
dmDays = 1
feWork = True
feDays = 1
days = 1
while True:
    if X <= 0:
        print(days - 1)
        break
    if dmDays == K:
        dmWork = False
        dmDays = 1
    if dmWork:
        X -= A
        dmDays += 1
    dmWork = True
    if feDays == M:
        feWork = False
        feDays = 1
    if feWork:
        X -= B
        feDays += 1
    feWork = True
    days += 1

@Fudthhh · 01.06.2020, 14:27

Антон255, Должно работать:

Python
1
2
3
4
5
6
7
8
9
10
11
12
a, k, b, m, x = 2, 4, 3, 3, 25
 
 
day = 0
while x > 0:
    if (day + 1) % b != 0:
        x -= a
    if (day + 1) % m != 0:
        x -= k
    day += 1
 
print(day) # 7

@Антон255 · 01.06.2020, 15:31 **[ТС]**

Спасибо

@Viktorrus · 01.06.2020, 15:39

Антон255, По правилам форума, если Вам подходит решение, которое дал Вам DmFat, то пометьте его комментарий как лучший ответ. Это добавит ему единичку к рейтингу. Это и будет Вашей благодарностью за помощь.
А так же у Вашей темы будет поставлена галочка, что будет информировать других людей, что задача решена.

@Вадим Тукаев · 02.06.2020, 16:29

Дмитрий срубает за D дней (D - D // K) * A деревьев. Аналогично, Фёдор за те же D дней срубает (D - D // M) * B деревьев.

У нас есть простая формула для вычисления деревьев из дней, а нам надо наоборот, дни из деревьев. Очевидно, что чем больше дней, тем больше деревьев, т.е. у нас неубывающая функция, а значит, можно применить бинарный поиск.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def gen_trees(a, k, b, m):
    return lambda d: (d - d // k) * a + (d - d // m) * b
 
a, k, b, m, x = map(int, input().split(maxsplit=4))
trees = gen_trees(a, k, b, m)
 
lim = 1
while trees(lim) < x:
    lim *= 2
bas = lim // 2 + 1
lim -= bas - 1
 
while lim:
    p = bas + lim // 2
    t = trees(p)
    if t < x:
        bas = p + 1
        lim -= 1
    lim //= 2
 
print(bas)

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

@Антон255 1 / 1 / 0 Регистрация: 03.08.2018 Сообщений: 27
	01.06.2020, 15:31 [ТС]
	Спасибо 0

@Viktorrus 1732 / 970 / 199 Регистрация: 22.02.2018 Сообщений: 2,693 Записей в блоге: 6
	01.06.2020, 15:39
	Антон255, По правилам форума, если Вам подходит решение, которое дал Вам DmFat, то пометьте его комментарий как лучший ответ. Это добавит ему единичку к рейтингу. Это и будет Вашей благодарностью за помощь. А так же у Вашей темы будет поставлена галочка, что будет информировать других людей, что задача решена. 0

Вырубка Леса

Решение