Вырубка леса

@Rorik · Регистрация: 28.06.2020

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

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут 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≤109 , 2≤K,M≤1018, 1≤X≤1018).

Выходные данные

Выведите одно целое число — искомое количество дней.

Пояснения к примеру

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:

1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.
Примеры
Ввод
Вывод
2 4 3 3 25
7
Вот мой код, он работает, но превышает время работы

Python
1
2
3
4
5
6
7
8
9
10
11
12
a, k, b, m, x = map(int, input().split())
days = 0
while x > 0:
    days += 1
    if days % k != 0 and days % m == 0:
        x -= a
    elif days % m != 0 and days % k == 0:
        x -= b
    elif days % m != 0 and days % k != 0:
        x -= a
        x -= b
print(days)

Помогите пожалуйста ускорить, хотя бы совет каким способом/алгоритмом перерешать, спасибо

@Gdez · 05.08.2020, 05:15

Обычный бинарный поиск с функцией ОК:

Python
1
2
OK = (a * (M - M//k) + b * (M - M//m)
if OK < x :

@Rorik · 05.08.2020, 11:50 **[ТС]**

Gdez, спасибо большое за совет, все прошло)
Вот код, если кому нужно

Python
1
2
3
4
5
6
7
8
9
10
a, k, b, m, x = map(int, input().split())
L = 0
R = x
while R - L > 1:
    M = (R + L) // 2
    if a * (M - M //k) + b * (M - M // m) < x:
        L = M
    else:
        R = M
print(R)

@Gdez · 05.08.2020, 11:54

Rorik, идеи с "Субботником" есть?

@Rorik · 05.08.2020, 13:05 **[ТС]**

пока нет(
Но вот нашёл решение на С++ и оно работает, осталось переписать, надеюсь получится

C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
 
using namespace std;
 
int n,t,c;
   
int check(int k,int a[])
{
    int kol=0,i=1;
    while(i<=n-c+1)
    if(a[i+c-1]-a[i]<=k)
    {
        kol++;
        i=i+c;
    }
        else i++;
    if(kol>=t) return 1;
    else return -1;
   
}
 
int main()
{
    int i,m,r,l,min;
    scanf("%d%d%d",&n,&t,&c);
    int a[n+1];
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    if(n==c)
    {
        printf("%d",a[n]-a[1]);
        return 0;
    }
    l=0;
    r=a[n]-a[1];
    min=r;
    while(l<r)
    {
        m=(l+r)/2;
        if(check(m,a)>0)
        {
            r=m;   
            if(m<min) min=m;
        }
       
        else l=m+1;
    }
    printf("%d",min);
    return 0;
}

@StillCF · 05.08.2020, 13:12

Gdez, есть на С++ Задача "Субботник"
Она принимается.

Попробовал переписать:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
def check(k, a):
    kol = 0
    i = 1
    while i < (n - c + 1):
        if (a[i+c-1]-a[i]) <= k:
            kol += 1
            i += c
        else:
            i +=1
    if kol >= t:
        return 1
    else:
        return -1
 
n, t, c = map(int, input().split())
a = []
 
for i in range(n):
    a.append(int(input()))
a.append(0)
a.sort()
 
if n == c:
    print(0)
else:
    l = 0
    r = a[n] - a[1]
    minimum = r
    while l < r:
        m = (l + r) // 2
        if check(m,a) > 0:
            r = m
            if m < minimum:
                minimum = m
        else:
            l = m + 1
            
    print(minimum)

Сириус не принимает (неправильный ответ)

@Rorik · 05.08.2020, 13:15 **[ТС]**

StillCF, Возможно, Вы допустили где-то ошибку, но я сам не вижу её

@StillCF · 05.08.2020, 13:52

Rorik, Нашел свою ошибку в 4 строке <=
Вот правильно

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
26
27
28
29
30
31
32
33
34
35
def check(k, a):
    kol = 0
    i = 1
    while i <= (n - c + 1):
        if (a[i+c-1]-a[i]) <= k:
            kol += 1
            i += c
        else:
            i += 1
    if kol >= t:
        return 1
    else:
        return -1
 
n, t, c = map(int, input().split())
 
a = [0]
for i in range(n):
    a.append(int(input()))
a.sort()
 
 
l = 0
r = a[n] - a[1]
minimum = r
while l < r:
    m = (l + r) // 2
    if check(m,a) > 0:
        r = m
        if m < minimum:
            minimum = m
    else:
        l = m + 1
        
print(minimum)

@Gdez · 05.08.2020, 14:11

Спасибо
Мне нужна была функция ОК
Из кода понял ее реализацию)))

Новые блоги и статьи Все статьи Все блоги /
Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определенном условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,318
	05.08.2020, 11:54
	Rorik, идеи с "Субботником" есть? 0

@Rorik 25 / 14 / 2 Регистрация: 28.06.2020 Сообщений: 50
	05.08.2020, 13:15 [ТС]
	StillCF, Возможно, Вы допустили где-то ошибку, но я сам не вижу её 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,318
	05.08.2020, 14:11
	Спасибо Мне нужна была функция ОК Из кода понял ее реализацию))) 0

Опции темы