Вырубка леса

@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

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

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

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

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

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