寻找“合适”数字的算法推理？

9 投票

4 回答

5430 浏览

数据工程师

提问于 2025-04-30 00:27

问题

福尔摩斯最近对他的死敌莫里亚蒂感到很紧张。他所有想要击败莫里亚蒂的努力都没有成功。这段时间，福尔摩斯正在和华生博士一起解决一个问题。华生提到，CIA最近在他们的超级计算机“野兽”上遇到了一些奇怪的问题。

今天下午，福尔摩斯收到了一张来自莫里亚蒂的便条，便条上说他已经给“野兽”装上了病毒。而且，便条上还印着一个数字N。经过一些计算，福尔摩斯发现，去除病毒的关键是找到一个有N位数的最大“体面”数字。

一个“体面”数字的要求是：

只能包含数字3或5，或者同时包含这两个数字。
不允许有其他任何数字。
数字3出现的次数必须能被5整除。
数字5出现的次数必须能被3整除。

与此同时，摧毁“野兽”的倒计时正在快速进行。你能在福尔摩斯之前找到这个关键，拯救“野兽”吗？

输入格式第一行包含一个整数T，表示测试用例的数量。接下来的T行，每行包含一个整数N，即数字的位数。

输出格式输出一个有N位的最大体面数字。如果不存在这样的数字，就告诉福尔摩斯他错了，输出'-1'。

约束条件 1<=T<=20 1<=N<=100000

示例输入

示例输出

-1
555
33333
55555533333

解释对于N=1，没有这样的数字。

对于N=3，555是唯一可能的数字。

对于N=5，33333是唯一可能的数字。

对于N=11，55555533333及其所有数字的排列都是有效数字，其中给定的数字是最大的。

答案

for _ in range(int(input())):
    n = int(input())
    c = 5*(2*n%3)
    if c > n:
        print(-1)
    else:
        print('5' * (n-c) + '3'*c)

问题

有人能解释一下这个逻辑吗？特别是'c'变量的赋值是做什么的？

来源： https://www.hackerrank.com/challenges/sherlock-and-the-beast

暂无标签

4 个回答

x = int(raw_input())
while x!= 0 :
    y=int(raw_input())
    z=y
    while(z%3!=0):
        z-=5
    if(z<0):
        print '-1'
    else:
        print z*'5'+(y-z)*'3'
    x = x-1

如果一个数字（比如66317）不能被3整除，它的余数会是0、1或2中的一个。如果我把这个数字减去5，实际上就是在把它变成3的倍数，同时剩下的数字会是5的倍数，因为我是在从这个数字中减去5。

余数为0意味着这个数字可以被整除；余数为1意味着需要减去5两次；余数为2意味着只需要减去5一次。

回答于 2025-04-30 由 Python大师

分享举报

我觉得数学在这方面帮了我一点，我也查了一些相关的知识和历史。我的解决方案第一次就通过了所有15个测试，所以虽然我没有直接用到数学，但我的思路可能会对你有帮助。我把10及以下的情况当作特殊情况处理，这些我直接写死在代码里。对于10以上的数字，我把它们除以3，这样可以得到最多的“555”。当然，除以3后，余数只能是0、1或2。余数为0时，意味着就写555多少次。余数为1时，意味着要减去3个555，这样就能留出10个位置给10个3。余数为2时，意味着减去1个555，这样就剩下5个位置可以放一个33333。

对于余数，我用了3个if语句。对于特殊情况，我用了10个if语句。还有1个if语句是用来处理限制条件的。

回答于 2025-04-30 由 Python大师

分享举报

好的，思路大概是这样的。

首先，确定你想要多少个 5 和多少个 3。然后，把 5 放在前面。这样排列不会影响数字的好坏，但如果 5 在前面，数字会更大。
你想要的 3 的数量应该是满足条件的最小值，这样你就能有更多的 5，从而得到更大的数字。
你选择的 3 的数量必须是 5 的倍数。这意味着你最多只需要考虑 0、5 或 10 个 3。因为你希望剩下的数字数量能被 3 整除，以满足其他条件。如果 15 个 3 可行，那么 0 个 3 也可以；如果 20 个可行，那么 5 个也可以；如果 25 个可行，那么 10 个也可以。一般来说，从 3 的数量中减去 15，之前满足的条件仍然会被满足。
因此，5 的数量应该是 n-0、n-5 或 n-10，我们希望找到一个能被 3 整除的数量。计算 c = 5*(2*n%3) 会给你 0 个 3，所以如果 n 已经能被 3 整除，你就会有 n 个 5；如果 n 比 3 的倍数多 1，那么你会有 10 个 3，因此会有 n-10 个 5，而且 n-10 仍然能被 3 整除；依此类推。
唯一需要测试的是计算出的 c 个 3 和 n-c 个 5 是否满足隐含条件，即 n-c 应该是非负的。如果是负数，那就没有解；如果是非负的，那就是一个有效的解，把 5 放在前面会给你最大的解。

这是一个相对广泛的“编程”问题，测试的并不是你能否写出能完成工作的代码，而是看你能否通过逻辑推理将问题简化到一个简单的程度，从而高效地解决它。

回答于 2025-04-30 由 Python大师

分享举报

一个数学解决方案：

设 a 为 '5' 的数量，b 为 '3' 的数量。那么我们可以写成：

a + b = N

我们知道 a 能被 3 整除，b 能被 5 整除，所以可以设 a = 3n，b = 5m。

3n + 5m = N

这就是一个丢番图方程（http://en.wikipedia.org/wiki/Diophantine_equation），其中一个解是 (n0, m0) = (2N, -N)，而一般解为：

(n,m) = (5k + 2N, 3k - N)，k 为任意整数

现在的问题是要最小化 3k - N 的值（因为你想要更多的 '5'），使得 3k - N > 0。这就相当于找出 k，使得 3k 是比 N 大的下一个 3 的倍数。

举个例子，如果 N = 10 或 11，我们要找 3k = 12，也就是 k = 4。

因此，3k - N 就是 N 和下一个 3 的倍数之间的距离。这个解的作者声称 3k - N = 2N % 3，你可以通过穷举法来证明这一点，评估 N % 3 = 0、1 和 2 的情况。值得一提的是，表达式 '2N % 3' 中的 '2' 不是唯一的，它适用于序列 2、5、8、11... 中的任何数字，至于作者为什么选择这个特定的表达式，我就不清楚了。

你也可以从这个角度考虑 N % 3，表示 N 离下一个更小的 3 的倍数有多近。

回答于 2025-04-30 由 Python大师

分享举报

寻找“合适”数字的算法推理？

问题

示例输入

示例输出

答案

问题

4 个回答

撰写回答