Codeforces Global Round 27 |
---|
Закончено |
Вы сражаетесь с монстром со здоровьем $$$z$$$, используя оружие с уроном $$$d$$$. Изначально $$$d=0$$$. Вы можете выполнять следующие действия.
Вы не можете выполнять первую операцию более $$$k$$$ раз подряд.
Найдите минимальное количество монет, необходимое для того, чтобы победить монстра, нанеся ему хотя бы $$$z$$$ урона.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит 4 целых числа $$$x$$$, $$$y$$$, $$$z$$$ и $$$k$$$ ($$$1\leq x, y, z, k\leq 10^8$$$) — стоимость первой операции, стоимость второй операции, здоровье монстра и ограничение на первую операцию.
Для каждого набора входных данных выведите минимальное количество монет, необходимое для победы над монстром.
42 3 5 510 20 40 51 60 100 1060 1 100 10
12 190 280 160
В первом наборе входных данных $$$x = 2$$$, $$$y = 3$$$, $$$z = 5$$$ и $$$k = 5$$$. Вот стратегия, которая обеспечивает наименьшую возможную стоимость в $$$12$$$ монет:
Вы наносите в общей сложности $$$3 + 3 = 6$$$ урона, побеждая монстра, который имеет $$$5$$$ здоровья. Суммарное количество монет, которое вы потратите, составляет $$$2 + 2 + 2 + 3 + 3 = 12$$$ монет.
Во втором наборе входных данных $$$x = 10$$$, $$$y = 20$$$, $$$z = 40$$$ и $$$k = 5$$$. Вот стратегия, которая позволяет достичь наименьшей возможной стоимости в $$$190$$$ монет:
Всего вы нанесли $$$5 + 35 = 40$$$ урона, победив монстра, у которого ровно $$$40$$$ здоровья. Вы потратили $$$50 + 20 + 20 + 100 = 190$$$ монет.
Название |
---|