python - 使用 Python 解决编程竞赛

Question

很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它， visit the help center 。

已关闭 12 年前。

我发现了这个问题，我认为解决这个问题很有趣，但无法真正想出正确的解决方案 -

Inside a room, there is a monster with N heads, and a human (with 1 head). The human has two laser guns. The first gun, A destroys C1 heads when fired and the second gun,B destroys C2 heads when fired [The guns may destroy both the monster's as well as human heads, but the guns prioritize monster heads over human ones].

Also, if after the firing of the gun the monster has a positive non-zero number of heads left, the monster will grow additional heads. The monster grows G1 heads when gun A is used and it grows G2 heads when gun B is used.

The problem is to input N, C1, C2, G1 and G2, then find out what would be the shortest combination of gun-choice(A or B) the human must use to kill the monster(the monster dies when No. of heads=0). [Note- this problem is from a programming contest that has already ended]

我尝试使用递归来解决这个问题，但发现自己对如何实际提出解决方案一无所知。因此，如果您能给出一些如何解决该问题的提示，那就太好了。

Answer 1

首先:Dijkstra 的解决方案不是最佳解决方案:)

鉴于这句话:“枪可以摧毁怪物和人类的头”
我认为如果你能射击 10 个头，而怪物只有 5 个头，你就不能杀死它，因为那也会杀死你。那是对的吗？

无论如何，任何解决方案都将采用以下形式:
ABABAABBABBB...(A 和 B 的某些字符串)

最后一击时，你杀死 C1 或 C2 头。每次击中你都会杀死 C1 - G1 或 C2 - G2 头。

如果最后一击来自 A，则您必须用造成 (C1-G1) 或 (C2-G2) 伤害的射击摧毁 N-A 头。
如果最后一击来自 B，则必须用造成 (C1-G1) 或 (C2-G2) 伤害的射击摧毁 N-B 头。

任何K都可以表示为以下形式:

X*i + Y*j = K

当然，X 和 Y 必须互质，等等。K 个头部可以被 i 次伤害 X 和 j 次伤害 Y 摧毁。

可以用扩展最大公约数算法求出i和j的值。

求解 X = (C1-G1)、Y = (C2-G2) 和 K = (N-A)
同时求解 X = (C1-G1)、Y = (C2-G2) 和 K = (N-B)
最小的答案是正确的:)

就是这样:)