硬币束

Coin Bundle

专题: Brainteaser / 脑筋急转弯
难度: L3
来源: OpenQuant

题目详情

给你一堆 100 个硬币。你可以将这些硬币排列成任意数量的硬币，并且可以将任意数量的硬币放入每堆中。你的支出将是所有硬币堆中硬币数量的乘积。

例如，如果你制作了三叠大小分别为 20、20 和 60 的筹码，则你的奖金为 20 x 20 x 60 = 24000。硬币的最佳排列将为你带来 $a * b^c$ 的支出，其中 $a$ 和 $b$ 是相对质数。查找 $a$ 、 $b$ 和 $c$ 。

You are given a pile of 100 coins. You may arrange these coins into however many stacks you want and you may put as many coins into each stack as you would like. Your payout would be the product of the number of coins among all of the stacks.

For example, if you make three stacks of sizes 20, 20, and 60, your payout is 20 x 20 x 60 = 24000 . The optimal arrangement of the coins will give you a payout of $a * b^c$ , where $a$ and $b$ are relatively prime. Find $a$ , $b$ and $c$ .

解析

我们解决这个问题的目标是最大化产品。让我们从 10 叠每叠 10 个硬币的简单配置开始。如果我们将每个 10 的堆栈分成两个 5 的堆栈，那么我们会得到一个更大的乘积，因为每个 10 的堆栈现在为我们的乘积贡献 $5 * 5 = 25$ ，而不是 $10$ 。因此，我们现在有5个20个堆栈。但是，作为 $5 = 3 + 2$ 和 $3 * 2 = 6 > 5$ ，我们应该再次划分堆栈。

现在，我们将尝试尽可能多地堆叠 3 个。这将产生 33 叠 3 枚硬币和一枚额外的硬币。然而，这并不是最优的，因为移除我们的 3 叠硬币中的一叠并将其与单独的硬币放在一起会产生 $4 * 3^{32} > 3* 3^{32} = 3^{33}$ 。由于我们无法将 4 分成更优化的值，因此我们的解决方案是 $4 * 3^{32}$ ，因此答案是 $4, 3, 32$

Original Explanation

Our goal with this question is to maximize the product. Let's start with the simple configuration of 10 stacks with 10 coins each. If we divide each stack of 10 into two stacks of 5, then we get a larger product, as each stack of 10 now contributes $5 * 5 = 25$ to our product instead of $10$ . Therefore, we now have 5 stacks of 20. However, as $5 = 3 + 2$ and $3 * 2 = 6 > 5$ , we should divide the stacks again.

Now, we are going to try as many stacks of 3 as possible. This would yield 33 stacks of 3 and one extra coin. However, this is not optimal, as removing one of our stacks of 3 and putting it with the lone coin yields $4 * 3^{32} > 3* 3^{32} = 3^{33}$ . As we can't divide 4 into anything more optimal, our solution is $4 * 3^{32}$ , so the answer is $4, 3, 32$