Гомер Симпсон

@_qikert · Регистрация: 16.11.2019

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

Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: 1MNT1000000, все числа целые.

Входные данные
В первой строке находятся три числа - M, N и T, разделённые пробелами.

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

Помогите решить!
Вот мой код:

Python
1
2
3
4
5
6
7
8
9
10
11
line = input().split()
m = int(line[0])
n = int(line[1])
t = int(line[2])
min_mn = min(m, n)
max_num = t // min_mn
res = t - (min_mn * max_num)
if res == 0:
    print(max_num)
else:
    print(max_num, res)

Рыжий Лис · 29.12.2019, 13:36

Вроде, правильно. Я не смотрел, как считается остаток времени, но сама идея верна: сжираем по-максимуму ту еду, которую можно съесть быстрее. Потом бы ещё проверить, можно ли съесть другую еду или ужё времени не хватит.

@udeep · 29.12.2019, 15:22

"... чтобы потраченное время было как можно больше..."

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
m, n, t = map(int, input().split())
#m, n, t = (5, 4, 26)
#m, n, t = (2, 4, 36)
#m, n, t = (5, 4, 36)
 
x, y = (m, n) if m < n else (n, m)
if y % x: 
    k = (t % x) // (y % x)
    delta = t - k * y
    z = delta // x
    result = k + z
    delta -= z * x
    #print(f'{k}*{y} + {z}*{x} = {t - delta}')
else:
    result = t // x
    delta = t % x
    
print(result, delta if delta else '')

@_qikert · 29.12.2019, 20:44 **[ТС]**

неверное решение, ибо при 7, 10, 999 ответ неверен, 999 = 137 * 7 + 10 * 4 и остаток по времени 0, а в вашей проге 2.

Добавлено через 23 секунды
неверное решение, ибо при 7, 10, 999 ответ неверен, 999 = 137 * 7 + 10 * 4 и остаток по времени 0, а в моей проге 2.

Добавлено через 58 секунд
Проблема в том что остатки зацикливаются, в этом у меня и проблема не знаю, как реализовать, не могли-бы помочь?

@udeep · 29.12.2019, 23:37

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#m, n, t = map(int, input().split())
m, n, t = (7, 10, 999)
 
x, y = (m, n) if m < n else (n, m)
if y % x and t % x:
    delta = t + 1
    for i in range(t // y):
        z = (t - i * y) % x
        if z < delta:
            delta = z
            k = i
        # повтор периода
        elif z == delta:
            break
    z = (t - k * y) // x
    result = k + z
    print(f'{k}*{y} + {z}*{x} = {t - delta}')
else:
    result = t // x
    delta = t % x
    
print(result, delta if delta else '')
print()

@udeep · 30.12.2019, 10:38

_qikert,
Поправил предыдущий вариант.

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
#m, n, t = map(int, input().split())
m, n, t = (10, 7, 999)
 
x, y = (m, n) if m < n else (n, m)
delta = t % x
if y % x and delta:
    delta = t + 1
    for i in range(t // y):
        z = (t - i * y) % x
        if z < delta:
            delta = z
            k = i
            # 0
            if not delta:
                break
        # повтор периода
        elif z == delta:
            break
    z = (t - k * y) // x
    result = k + z
    print(f'{k}*{y} + {z}*{x} = {t - delta}')
else:
    result = t // x
    
print(result, delta if delta else '')

@_qikert · 30.12.2019, 10:53 **[ТС]**

всё решение хорошее, но как сделать, чтобы вывод был без пробела, когда остаток времени 0?
Пример:
2 4 1000
500 (есть пробел, а он не нужен)
PS уже всё понял можешь не писать

@ioprst · 30.12.2019, 10:56

Если выводится строка, то можно использовать rstrip.

@udeep · 30.12.2019, 10:59

_qikert,
Как и было у вас:

Python
1
2
3
4
if delta:
    print(result, delta)
else:
    print(result)

@_qikert · 30.12.2019, 11:03 **[ТС]**

Пока не монимаю в чём именно ошибка, но пишет в 2 тестах:'Ошибка во время выполнения программы'

@udeep · 30.12.2019, 11:17

_qikert,
Входные данные есть?
Код правили "под себя"?

+ Возможно n и\или m в данных тестах > t? Т.е. следует добавить соответствующую проверку...

@_qikert · 30.12.2019, 18:32 **[ТС]**

Сообщение от _qikert

всё решение хорошее, но как сделать, чтобы вывод был без пробела, когда остаток времени 0?
Пример

да, это я уже давно исправил, но после этого исправления появляются ошибки в других тестах, хз плчмеу

@_qikert · 01.01.2020, 16:50 **[ТС]**

Не могли бы помочь) Робот K-79

@_qikert · 02.01.2020, 16:56 **[ТС]**

Привет, крч я нашел входные данне при которых программа у тебя не работает: 6 5 7 вывод: 1 2. Можешь
справить?

Рыжий Лис · 02.01.2020, 17:06

Сообщение от _qikert

не работает: 6 5 7 вывод: 1 2.

А что не так? 7-5*1=2

1 2

Сообщение от _qikert

Предпочтителен вариант, когда дополнительного времени остаётся как можно меньше.

Минимизировать остаток не требуется.

@_qikert · 02.01.2020, 18:12 **[ТС]**

как раз в программе требуется найти вариант при котором остаток времени, как можно меньше, а уже второй приоритет кол-во чизб и гамб

Добавлено через 56 минут
Я тут порылся в инете и нашел такое решение, о не особо его понимаю не могли бы помочь написать код
----------------------------
Максимальное число гамбургеров составляет K = T div N, а чизбургеров L = T div M. Двойной цикл до K и L по трудоемкости вычислений нас устроить не может.

В [2] указан следующий простой выход. Если съедается I гамбургеров, то число чизбургеров определяется как J = (T - I × N) div M. Значит, достаточно одинарного цикла.

Но и такой подход не годится для заданной размерности. Пусть, например, M ≤ N. Очевидно, что максимальное суммарное число гамбургеров и чизбургеров составляет P = T div M. Как минимизировать остаток времени? Нужно вместо части гамбургеров съесть чизбургеры. Каждый из них потребует N - M из остатка времени. Значит, их можно съесть Q = (T - P × M) div (N - M). Тогда число гамбургеров уменьшится и составит P- Q.

Рыжий Лис · 02.01.2020, 18:16

Python
1
2
3
4
assert m <= n
p = t % m
q = (t - p * m) % (n - m)  # число чиз…
q2 = p - q  # число гам...

@udeep · 03.01.2020, 09:40

Сообщение от _qikert

Привет, крч я нашел входные данне при которых программа у тебя не работает: 6 5 7 вывод: 1 2. Можешь
справить?

~~for i in range(t // y):~~
for i in range(t // y + 1):

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте 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 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	29.12.2019, 13:36
	Вроде, правильно. Я не смотрел, как считается остаток времени, но сама идея верна: сжираем по-максимуму ту еду, которую можно съесть быстрее. Потом бы ещё проверить, можно ли съесть другую еду или ужё времени не хватит. 0

@_qikert 34 / 25 / 8 Регистрация: 16.11.2019 Сообщений: 179
	29.12.2019, 20:44 [ТС]
	неверное решение, ибо при 7, 10, 999 ответ неверен, 999 = 137 * 7 + 10 * 4 и остаток по времени 0, а в вашей проге 2. Добавлено через 23 секунды неверное решение, ибо при 7, 10, 999 ответ неверен, 999 = 137 * 7 + 10 * 4 и остаток по времени 0, а в моей проге 2. Добавлено через 58 секунд Проблема в том что остатки зацикливаются, в этом у меня и проблема не знаю, как реализовать, не могли-бы помочь? 0

@_qikert 34 / 25 / 8 Регистрация: 16.11.2019 Сообщений: 179
	30.12.2019, 10:53 [ТС]
	всё решение хорошее, но как сделать, чтобы вывод был без пробела, когда остаток времени 0? Пример: 2 4 1000 500 (есть пробел, а он не нужен) PS уже всё понял можешь не писать 0

@ioprst 1303 / 843 / 409 Регистрация: 12.03.2018 Сообщений: 2,305
	30.12.2019, 10:56
	Если выводится строка, то можно использовать rstrip. 0

@_qikert 34 / 25 / 8 Регистрация: 16.11.2019 Сообщений: 179
	30.12.2019, 11:03 [ТС]
	Пока не монимаю в чём именно ошибка, но пишет в 2 тестах:'Ошибка во время выполнения программы' 0

@udeep 55 / 40 / 18 Регистрация: 16.12.2019 Сообщений: 149
	30.12.2019, 11:17
	_qikert, Входные данные есть? Код правили "под себя"? + Возможно n и\или m в данных тестах > t? Т.е. следует добавить соответствующую проверку... 0

@_qikert 34 / 25 / 8 Регистрация: 16.11.2019 Сообщений: 179
	01.01.2020, 16:50 [ТС]
	Не могли бы помочь) Робот K-79 0

@_qikert 34 / 25 / 8 Регистрация: 16.11.2019 Сообщений: 179
	02.01.2020, 16:56 [ТС]
	Привет, крч я нашел входные данне при которых программа у тебя не работает: 6 5 7 вывод: 1 2. Можешь справить? 0

@_qikert 34 / 25 / 8 Регистрация: 16.11.2019 Сообщений: 179
	02.01.2020, 18:12 [ТС]
	как раз в программе требуется найти вариант при котором остаток времени, как можно меньше, а уже второй приоритет кол-во чизб и гамб Добавлено через 56 минут Я тут порылся в инете и нашел такое решение, о не особо его понимаю не могли бы помочь написать код ---------------------------- Максимальное число гамбургеров составляет K = T div N, а чизбургеров L = T div M. Двойной цикл до K и L по трудоемкости вычислений нас устроить не может. В [2] указан следующий простой выход. Если съедается I гамбургеров, то число чизбургеров определяется как J = (T - I × N) div M. Значит, достаточно одинарного цикла. Но и такой подход не годится для заданной размерности. Пусть, например, M ≤ N. Очевидно, что максимальное суммарное число гамбургеров и чизбургеров составляет P = T div M. Как минимизировать остаток времени? Нужно вместо части гамбургеров съесть чизбургеры. Каждый из них потребует N - M из остатка времени. Значит, их можно съесть Q = (T - P × M) div (N - M). Тогда число гамбургеров уменьшится и составит P- Q. 0