Question

Миссия простая: нужно либо накопить c кредитов (читайте: единиц вымышленной валюты), либо сокрушить врага в этом регионе. миссия проходная и не интересная (даже никаких юнитов кроме пехоты), так что надо её закрыть побыстрее. изначально у нас нет ни одного кредита и ни одного отряда пехоты. но есть база и гарантия того, что враг нас не обнаружит, пока мы на него не нападём. на нашей базе можно хранить не более x кредитов. Чтобы хранить больше, нужно строить хранилища: каждое стоит y (y≤x) кредитов и в каждом можно будет хранить дополнительно по максимум z кредитов. Строительство моментально (а вы что, реализма ожидали?). Через каждые m минут нам привозят добычу на s кредитов. Добыча моментально конвертируется в кредиты и мы перераспределяем новые s кредитов и кредиты, имеющиеся на базе, по трём направлениям: строительство хранилищ, наём отрядов пехоты, хранение на базе. Количество кредитов, отданных на строительство хранилищ, должно быть кратно стоимости постройки одного хранилища. Количество кредитов, отданных на наём отрядов пехоты, должно быть кратно стоимости наёма одного отряда пехоты. Если мы отдаём на хранение больше кредитов, чем может храниться на базе (хранилища, на строительство которых мы только что отдали кредиты, тоже учитываются), то излишки кредитов исчезают.Если после очередного описанного выше распределения на базе будет храниться хотя бы c кредитов, то считается, что мы накопили c кредитов, и миссия считается пройденной.Один отряд пехоты стоит f (f≤x) кредитов. Сразу после оплаты, которая тоже моментальна, отряд будет ждать приказаний на нашей базе.Проще и быстрее всего избавиться от врага в этом регионе – заставить его капитулировать. Для этого нужно привести к стенам вражеской базы больше отрядов пехоты, чем есть на вражеской базе. По данным разведки, на вражеской базе e отрядов, а добраться до вражеской базы наши отряды пехоты смогут за t минут (все отряды, независимо от их количества, могут идти вместе).За сколько в лучшем случае мы завершим миссию?Формат входных данныхЕдинственная строка содержит 9 целых чисел c,x,y,z,m,s,f,e,t (1≤c,x,y,z,m,s,f,e,t≤100;f,y≤x).Формат выходных данныхВыведите одно целое число – искомое количество минут.Пояснение к примеруЧтобы максимально быстро накопить 2700 кредитов, мы можем построить 2 хранилища через 3 минуты после начала (в этот момент у нас появятся первые кредиты) и далее просто складировать все кредиты на базе. Тогда через 9 минут после начала на базе накопится необходимая сумма.Чтобы заставить врага сдаться, мы можем через 3 минуты после начала нанять 10 отрядов пехоты и сразу же пойти на вражескую базу. Тогда через 6 минут после начала враги сдадутся.Несмотря на то, что пример не удовлетворяет ограничениям на входные данные в данной подзадаче, для получения баллов за текущую подзадачу необходимо, чтобы ваша программа выдавала правильный ответ на пример.Sample Input:2700 1000 150 1000 3 1000 100 7 3Sample Output:6Напишите программу. Тестируется через stdin → stdout​

Answer 1

Ответ:

import math

c,x,y,z,m,s,f,e,t = map(int, input().split())

a = math.ceil((e + 1) * f / s) * m + t

if c>x:

   n = math.ceil((c - x) / z)

else:

   n = 0

b = math.ceil((c+n*y)/s)*m

print(min(a,b))

Объяснение:

Более простой код. Правда работает только на первых двух. На третьем даёт ошибку в 45 тесте(

Answer 2

Приведенная задача является оптимизационной задачей, и ее можно решить с помощью применения жадного алгоритма. В этом случае, мы будем каждую минуту принимать решение о том, что делать: строить хранилища, наем отрядов пехоты или отправлять отряды к вражеской базе. Мы будем продолжать принимать решения до тех пор, пока не выполнится одно из двух условий: либо мы накопим достаточное количество кредитов, либо отправим достаточное количество отрядов пехоты, чтобы заставить врага капитулировать.

Вот пример решения на языке Python:

pythonCopy code
def mission_time(c, x, y, z, m, s, f, e, t):
    credits = 0  # текущее количество кредитов
    storage = 0  # текущее количество кредитов, хранимых на базе
    infantry_units = 0  # текущее количество отрядов пехоты

    time = 0  # текущее время

    while True:
        time += 1

        # Распределение кредитов и добычи
        if time % m == 0:
            credits += s
            available_storage = min(storage, x)
            storage -= available_storage
            credits += available_storage

        # Проверка условий завершения миссии
        if credits >= c:
            return time

        if infantry_units >= e:
            return time

        # Принятие решений
        if credits >= y and storage + z <= x:
            num_storages = credits // y
            storage += num_storages * z
            credits -= num_storages * y

        if credits >= f:
            num_units = min((t - time) // t, credits // f)
            infantry_units += num_units
            credits -= num_units * f

        # Отправка отрядов к вражеской базе
        if infantry_units >= e:
            return time


# Чтение входных данных
input_data = input().split()
c = int(input_data[0])
x = int(input_data[1])
y = int(input_data[2])
z = int(input_data[3])
m = int(input_data[4])
s = int(input_data[5])
f = int(input_data[6])
e = int(input_data[7])
t = int(input_data[8])

# Вызов функции и вывод результата
result = mission_time(c, x, y, z, m, s, f, e, t)
print(result)

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