Question

您希望尽快输入 200 个“X”。以下每个过程需要 1 秒：

输入 1 “X”

⁠复制你所写的内容

⁠粘贴你复制的内容

达到至少 200 个“X”的最快方法是什么？

我的答案是：先输入两个 X（+2 秒），复制并粘贴 3 次（+4 秒），现在复制所有这些并粘贴 4 次（+5 秒）。现在我们有 80 个 X。接下来我们复制并粘贴 2 次（+3 秒）。现在我们有 240 个 X。

总的来说，这个策略需要 14 秒。

这是正确答案吗？有没有更具体、更严谨的方法来证明这一点？

确认一下，您需要输入至少200 个 X 吗？还是必须准确无误（在这种情况下您的尝试是不够的）？ — 
您的想法是：两个 X，然后是 8X，然后是 40X，而不是 80。使用此开始您需要 16 个步骤，而不是 14 个。 — 
$2 + 2 \times 3 = 8$ 2 + 2\times 3=8， $8 + 8 \times 4 = 40$ 8+8\times 4 = 40，不是 $80$ 80 — 
这是一个通过蛮力解决这个问题的脚本：。它找到了 TTTTCPCPPCPPCPP（15 秒）。 —

Answer 1

有趣！经过一番挖掘，我发现它与非常相似，@ajotatxe 和 @Andrea Marino 已经给出了一个很好的解决方案，你应该先阅读 – 我将在这里使用完全相同的方法。

定义 $S$ S其中 C、P 和 T 的字母（分别为复制、粘贴、键入）组成长度为 $n > 4$ n > 4这会最大化输入的“X”的数量。我们规定 $n > 4$ n > 4以免担心退化的情况。为了解决您的问题，我们将找到任意输入的最大数量的“X” $n$ n。让我们从一个关键的观察开始：

$S$ S以 TT 或 TTT 开始，然后专门使用 C 或 P。

那 $S$ S以 TT 或 TTT 开头的字符串可以通过暴力破解所有可能性来查看 $n \leq 4$ n \leq 4（TTCP 有 4 个字母输入，剪贴板中有 2 个字母，而 TTTC 有 3 个字母输入，剪贴板中有 3 个字母。其他所有组合输入的字母较少，剪贴板中的字母也较少）。然后，由于剪贴板中至少会有 2 个字母，因此粘贴总是更好的选择 $\geq 2$ \geq 2字母比输入 1 个字母要多。

现在，不要将字符串的剩余部分视为 C 和 P，而是将其视为 CkP 的“块”，其中我使用“CkP”来表示 C 后跟 k 个 P。这给了我们一个非常有用的属性：

这些 CkP 的顺序 $S_{n}$ S_n不要紧。

请注意，每个 CkP 只是乘以“X”的数量，因此这些的顺序并不重要，因为乘法是可交换的。让 $A$ A是 $S$ S打字后（因此它完全由 $S$ S的 CkP），并定义 $m$ m的长度 $A$ A我们可以想到 $A$ A作为无序列表的整数，每个整数对应一个特定的 CkP。

具体来说，每个 CkP 使用 k+1 个字母，并将“X”的数量乘以 k+1；渐近地，这意味着 CkP 中的每个字母将“X”的数量乘以 $\sqrt[k + 1]{k + 1}$ \sqrt[k+1]{k+1}. 使该乘积因子最大的整数是 $k = 2$ k=2，因此我们预计大部分 $S_{n}$ S_n将被 C2P 占据。事实上，经过另一次强力攻击后，我们可以找到每个 $m$ m：

如果 $m = 3 a$ m = 3a，然后 $A$ A仅由 $a$ aC2P，因此“X”的数量乘以 $3^{a}$ 3^a。
如果 $m = 3 a + 1$ m = 3a + 1，然后 $A$ A包括一个 C3P 和 $a - 1$ a-1C2P，因此“X”的数量乘以 $4 \times 3^{a - 1}$ 4 \times 3^{a-1}。
如果 $m = 3 a + 2$ m = 3a + 2，然后 $A$ A包括一个 C1P 和 $a$ aC2P，因此“X”的数量乘以 $2 \times 3^{a}$ 2 \times 3^a。

对于整数 $a$ a。现在我们快完成了；我们只需要考虑从哪个开始 $S$ S（TT 或 TTT）是最佳的；我们在下表中计算了可能的情况：

$\begin{array}{rr} T T + (n - 2) & T T T + (n - 3) \\ n = 3 a & 2 \times (4 \times 3^{a - 2}) & 3 \times 3^{a - 1} \\ n = 3 a + 1 & 2 \times (2 \times 3^{a - 1}) & 3 \times (4 \times 3^{a - 2}) \\ n = 3 a + 2 & 2 \times 3^{a} & 3 \times (2 \times 3^{a - 1}) \end{array}$ \begin{array} {|r|r|}\hline & {TT} + (n – 2) & {TTT} + (n – 3) \\ \hline n = 3a & 2 \times (4 \times 3^{a-2}) & 3 \times 3^{a-1} \\ \hline n = 3a+1 & 2 \times (2 \times 3^{a-1}) & 3 \times (4 \times 3^{a-2}) \\ \hline n = 3a+2 & 2 \times 3^a & 3 \times (2 \times 3^{a-1}) \\ \hline \end{array}

注意，当 $n = 3 a + 1$ n = 3a + 1或者 $n = 3 a + 2$ n = 3a + 2，无论哪个开始，生成的“X”数量都是相同的。然而，对于 $n = 3 a$ n = 3a，TTT 开头给出的“X”稍多一些，所以我们将使用它。这给了我们计算最大“X”数量的公式 $n > 4$ n > 4；

⎧ ⎩ ⎨ 3 一个 ， 4 \times 3 a - 1 ， 2 \times 3 一个 ， 如果 n = 3 ​ 如果 n = 3 a + 1 如果 n = 3 a + 2

\begin{cases}
3^a, & \text{if $n = 3a$} \\
4 \times 3^{a-1}, & \text{if $n = 3a + 1$} \\
2 \times 3^a, & \text{if $n = 3a + 2$}
\end{cases}

现在，对于 $n = 14$ n = 14，我们可以看到 $S$ S最多可得 $2 \times 3^{4} = 162$ 2 \times 3^4 = 162移动，而对于 $n = 15$ n = 15我们有 $S$ S最多可得 $3^{5} = 243$ 3^5 = 243移动。因此，获得 200 个 X 的最佳移动次数是 15（它看起来像 TTT 后面跟着四个 C2P，即 TTTCPPCPPCPPCPP）。

2 次使用 C1P 不是总是比 C3P 更好吗？两者似乎都使用 4 个字符乘以 4，但第一次使用会在剪贴板中留下更大的数字。虽然对于最佳解决方案来说，这可能实际上没有区别。编辑：是的，我明白，在真空中更好，但由于这两个序列后面都是 C2P 或最佳解决方案中的字符串末尾，因此剪贴板值无关紧要。 —

Answer 2

让 $C$ C表示复制， $P$ P表示粘贴，并且 $T$ T表示输入。那么序列 TTTCPPCPCPPCPCP 在 15 秒内实现了 216 个 X，比上面给出的解决方案快一秒。

值得注意的是，TTTCPP 给出了 9 个副本，而不是 TTCPPP 一开始实现的 8 个。

组合数学 – 尽可能快地输入 200 个 Xs

最佳答案
2

组合数学 – 尽可能快地输入 200 个 Xs

最佳答案 2

最佳答案
2