← 返回题目列表

Codeforces · 1413/E

E. 独奏中甲骨文

中文机器翻译题面 查看原题

Meka-Naruto 玩电脑游戏。他的角色具有以下能力:给定一个敌方英雄,对其造成 $$$a$$$ 即时伤害,然后在每秒结束时治疗该敌人 $$$b$$$ 生命值,持续 $$$c$$$ 秒,从使用该能力后一秒开始。这意味着,如果在$$$t$$$时间使用该能力,则由于该能力,敌人的生命值在$$$t$$$时间点减少$$$a$$$,然后在$$$t + 1$$$、$$$t + 2$$$、...、$$$t + c$$$时间点增加$$$b$$$。

该能力的冷却时间为 $$$d$$$ 秒,即。 e.如果梅卡鸣人在$$$t$$$时刻使用它,那么他下次可以使用它的时间是$$$t + d$$$。请注意,他只能在整数时间点使用该能力,因此敌人生命值的所有变化也只会在整数时间发生。

不同用途的能力所产生的效果可能会相互叠加;也就是说,当前处于 $$$k$$$ 法术下的敌人这次获得 $$$k\cdot b$$$ 治疗量。此外,如果多个健康变化同时发生,它们都会被同时计算在内。

现在梅卡·鸣人想知道他是否可以通过每次使用该能力(即每 $$$d$$$ 秒)来杀死敌人。如果敌人的生命值变为 $$$0$$$ 或更少,他们就会被杀死。假设除了 Meka-Naruto 的角色能力之外,敌人的生命值不会受到任何影响。梅卡鸣人能够杀死敌人的最大生命值是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^5$$$) 代表测试用例的数量。

每个测试用例用一行包含四个数字 $$$a$$$、$$$b$$$、$$$c$$$ 和 $$$d$$$ ($$$1\leq a, b, c, d\leq 10^6$$$) 分别表示即时伤害量、每秒治疗量、治疗次数和技能冷却时间来描述。

输出

对于单独行中的每个测试用例,如果该技能可以杀死具有任意数量生命值的敌方英雄,则打印 $$$-1$$$ ,否则打印可以杀死的敌人的最大生命值。

示例

输入 #1

7
1 1 1 1
2 2 2 2
1 2 3 4
4 3 2 1
228 21 11 3
239 21 11 3
1000000 1 1000000 1

输出 #1

1
2
1
5
534
-1
500000500000

注意

在示例的第一个测试用例中,每个单位的伤害都会在一秒内被取消,因此 Meka-Naruto 不能造成超过 1 个伤害。

在示例的第四个测试用例中,敌人得到:

- $$$4$$$ 伤害($$$1$$$-st 施法),时间 $$$0$$$;
- $$$4$$$ 伤害($$$2$$$-施法)和 $$$3$$$ 治疗($$$1$$$-施法),时间为 $$$1$$$(初始生命值总计 $$$5$$$ 伤害);
- $$$4$$$ 伤害($$$3$$$-nd 施法)和 $$$6$$$ 治疗($$$1$$$-st 和 $$$2$$$-nd 施法),时间为 $$$2$$$(对初始生命值的总伤害 $$$3$$$);
- 等等。

可以证明敌人没有一次受到总计 $$$6$$$ 或更多的伤害,因此答案是 $$$5$$$。请注意生命值是如何重新计算的:例如,$$$8$$$-生命值的敌人不会在$$$1$$$时间死亡,就好像我们首先从他的生命值中减去$$$4$$$伤害,然后认为他已经死亡,然后添加$$$3$$$治疗。

在第六个测试用例中,可以在足够的时间内杀死任意健康的敌人。

在第七个测试用例中,答案不适合 32 位整数类型。