algorithm - 如何修复不可能的 Osmos 关卡？

Question

我读了这个optimisation problem在谷歌代码挑战赛中。 (现在比赛已经结束了，聊聊也无妨。)

Armin is playing Osmos, a physics-based puzzle game developed by Hemisphere Games. In this game, he plays a "mote", moving around and absorbing smaller motes.

A "mote" in English is a small particle. In this game, it's a thing that absorbs (or is absorbed by) other things! The game in this problem has a similar idea to Osmos, but does not assume you have played the game.

When Armin's mote absorbs a smaller mote, his mote becomes bigger by the smaller mote's size. Now that it's bigger, it might be able to absorb even more motes. For example: suppose Armin's mote has size 10, and there are other motes of sizes 9, 13 and 19. At the start, Armin's mote can only absorb the mote of size 9. When it absorbs that, it will have size 19. Then it can only absorb the mote of size 13. When it absorbs that, it'll have size 32. Now Armin's mote can absorb the last mote.

Note that Armin's mote can absorb another mote if and only if the other mote is smaller. If the other mote is the same size as his, his mote can't absorb it.

You are responsible for the program that creates motes for Armin to absorb. The program has already created some motes, of various sizes, and has created Armin's mote. Unfortunately, given his mote's size and the list of other motes, it's possible that there's no way for Armin's mote to absorb them all.

You want to fix that. There are two kinds of operations you can perform, in any order, any number of times: you can add a mote of any positive integer size to the game, or you can remove any one of the existing motes. What is the minimum number of times you can perform those operations in order to make it possible for Armin's mote to absorb every other mote?

For example, suppose Armin's mote is of size 10 and the other motes are of sizes [9, 20, 25, 100]. This game isn't currently solvable, but by adding a mote of size 3 and removing the mote of size 100, you can make it solvable in only 2 operations. The answer here is 2.

如何解决？ (请用散文解释，而不是神秘的代码)

---

我认为“给定一个可行的解决方案，删除一个微尘大小 x 并添加一个更大的微尘大小 y，有一个更好的(至少同样好)可行的解决方案，其中添加的所有微尘都小于所有删除的微尘” (而不是删除 mote 大小 x，在较大的 mote 大小 y 之后吃掉它)

这表明了一种快速算法。从最小到最大对微尘进行排序。吃。如果卡住，记录“删除其余部分”作为潜在的解决方案。添加 motes size player - 1 直到大到足以吃掉我们卡住的微尘。重复。记录最终的“仅添加”解决方案。从记录的方案中选择最优方案。

我实现了 this algorithm in Python .我相当确定我的代码正确地实现了我的算法。我想我的算法错了？

Answer 1

我认为您的问题出在代码中:

# Let's add motes until we can eat it.
while A <= m:
  A += A-1
  operations += 1

这模拟了添加更多微尘，直到您大到可以吃掉当前的微尘为止，但之后您不吃它。

换句话说，我认为您需要将其更改为:

while A <= m:
  A += A-1
  operations += 1
A+=m

当你吃掉当前的那个时，以反射(reflect)增长。