找到“体面”的数字算法推理？
问题
夏洛克·福尔摩斯对莫里亚蒂教授变得多疑，他的主要敌人。他征服莫里亚蒂的一切努力都是徒劳的。这些天夏洛克正在和沃森医生解决一个问题。沃森提到中央情报局最近在他们的超级计算机“野兽”上遇到了一些奇怪的问题。
今天下午，夏洛克收到莫里亚蒂的一封短信，说他感染了一种病毒。此外，这张便条上印着N号。经过计算，夏洛克发现去除病毒的关键是拥有N位数的最大的“体面”数字。
一个“体面”的数字-
- 3或5或两者兼而有之。
- 不允许有其他数字。
- 出现3的次数可被5整除。
- 出现5的次数可被3整除。
与此同时，“野兽”被摧毁的计数器运行得非常快。你能救出“野兽”，然后在夏洛克之前找到钥匙吗？
输入格式第一行将包含一个整数T，测试用例的数量。后面跟着T行，每一行包含一个整数N，即数字中的数字数。
输出格式最大的体面数字有N位数。如果没有这样的号码，告诉夏洛克他错了，然后打印'-1‘
约束1<=T<=20 1<=N<=100000
样本输入
4
1
3
5
11样本输出
-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
Stack Overflow用户
发布于 2014-10-27 22:11:08
数学解：
设a=5，b=3，所以
a + b = N
我们知道，3除a，5除b，所以让a= 3n，b= 5m
3n+5m = N
这是一个丢番图方程(equation)，其中一个解是(n0，m0) = (2N，-N)，并且是通解。
(n,m) = (5k+2N, 3K-N), k any integer
现在的问题是最小化数量3k-N (，因为您想要更多的'5's)，这样3k-N > 0。这与从N找到3k的下一个倍数的k是一样的。
例如，如果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在这个意义上是如何接近3的下一个倍数的。
Stack Overflow用户
发布于 2014-10-27 21:17:12
好吧，这个想法是这样的。
- 一旦计算出需要多少个
5和多少个3，就应该先加载5s，排序对数字是否合适没有任何影响；但是如果5在前面，则会更大。 - 您想要的
3的数量应该是满足这些约束的最小数目，因为这样您就会有更多的5，从而得到一个更大的数目。 3s的数目必须被5整除。这意味着没有超过103s的任何点:您应该只考虑0、5或103s。这是因为您想要最小的数，使剩余的数字数可被3整除，以满足另一个约束。如果有15个3s工作，那么具有03s也一样；如果20个工作，那么5个工作；如果25个工作，那么10个工作。通常，从3s的数目中减去15个将使约束保持不变，如果它们是以前的话。- 因此，
5s的数目必须是n-0、n-5或n-10，我们希望给出一个可被3整除的数字。如果n已经被3整除，计算c = 5*(2*n%3)将给出03s，因此n5s；如果n已经可被3整除，则计算c = 5*(2*n%3)s；如果n-10s仍然可以被3整除，则n-10s大于3的倍数，在这种情况下，D33仍然可以被3除；等等。 唯一要测试的是c3s和n-c5s的计算是否满足n-c非负的隐式约束。如果它是负的，那么就没有解；如果它是非负的，那么这是一个有效的解决方案，并且前面加载5s会给出最大的这样的解决方案。
这是一个相当广泛的“编程”问题之一，测试并不是真正地查看是否能够写出一些完成这项工作的代码，而是看看是否可以将问题逻辑地减少到一个非常琐碎的问题，并且能够非常有效地解决。
Stack Overflow用户
发布于 2016-01-04 05:46:39
我认为数学有点帮助，我阅读了它的不同部分和历史。我的解决方案第一次通过了所有15个测试，所以虽然我没有使用数学，但我对这个问题的看法可能会对你有所帮助。我处理了10个或更少的边缘案件，我只是硬编码。任何高于10，我除以3，得到最多的“555”出局。当然，当除以3时，余数只能是0，1或2。当然，零意味着只写555次，但是很多次。第一种方法是减去555中的3，然后再回到10个打开的位置。两种方法是减去555 s中的1，为33333留出5个槽。
3如果剩余的话。边缘病例10例。1如果为约束。1名。
https://stackoverflow.com/questions/26596535
复制相似问题
腾讯云开发者
