質問

Consider the following game:

One day a castle is attacked at sunrise (by surprise) by n soldiers.

Each soldier carries a canon and a rifle.

The castle has strength s.

On the first day each soldier shoots his canon at the castle costing the castle n strength points (i.e. the castle ends the first day with s=s-n strength points). After all the soldiers have fired, the castle sends dpw defenders to battle them.

In the ensuing days the castle and the soldiers battle it out following these rules:

  1. All the soldiers fire first. A soldier can fire his canon at the castle or his rifle at one of the defenders (but not both and each soldier can only shoot once). One shot at a defender kills him. One shot at the castle decreases its strength by 1.
  2. Then each of the d defenders shoots at one soldier (and only one) killing him.

  3. If the castle still has strength points (i.e. s>0) it sends a new batch of dpw defenders at this point. The total number of defenders in the next round will be d=d+dpw.

  4. Repeat 1 through 3 on each new day.

  5. If all soldiers are killed by the defenders, the castle wins.

  6. If there are zero defenders after the soldiers shoot and the castle strength is zero, the soldiers win.

We would like to know the minimum number of rounds the soldiers need to win the game (or if not possible the minimum number of rounds for the castle to win the game).

We would also like to know the number of soldiers, defenders and castle strength at the beginning of each round for the minimum number of rounds solution.

An easy way to solve this problem seems to me to be by recursive backtracking/depth first search or dynamic programming.

The problem however seems simple enough that a better/faster solution seems likely to exist (one that doesnt involve a large search or maybe even a search at all).

Is it obvious what that better strategy/algorithm might be?

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top