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

@_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):

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

Рыжий Лис Просто Лис 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