寻找"decent"数字算法推理？

Question

问题

福尔摩斯对他的宿敌莫里亚蒂教授越来越偏执。他制服莫里亚蒂的所有努力都是徒劳的。这些天夏洛克正在和华生医生一起解决一个问题。Watson提到，美国中央情报局的超级计算机"野兽"最近一直面临着奇怪的问题。

今天下午，夏洛克收到莫里亚蒂的一封信，说他用病毒感染了"野兽"。此外，纸条上还印着数字N。经过计算，夏洛克发现，清除病毒的钥匙是最大的N位数"体面"数字。

一个"体面"号码有

• 3或5或两者都作为其数字
• 不允许使用其他数字
• 3出现的次数可以被5整除
• 5出现的次数可以被3整除

与此同时，对抗"野兽"毁灭的战斗正在迅速展开。你能拯救"野兽"，在夏洛克之前找到钥匙吗？

输入格式第一行将包含一个整数T，即测试用例的数量。后面跟着T行，每行包含一个整数N，即数字中的位数

输出格式有N个数字的最大十进制数。如果没有这样的号码，告诉夏洛克他错了，并打印"-1"

限制1<T<201<N<100000

样本输入

4
1
3
5
11

样本输出

-1
555
33333
55555533333

解释对于N=1，不存在这样的数字。

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

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

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

答案

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

Answer 1

一个数学解决方案：

设a='5'的len，b='3'的len。所以

a + b = N

我们知道3除a，5除b，所以设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 any integer

现在的问题是最小化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的下一个LOWER倍数的接近程度。

Answer 2

好吧，思路是这样的。

1. 一旦你计算出你想要多少5和多少3，你就应该预先加载5。排序对数字是否合适没有任何影响；但如果CCD_ 7在前面，它会更大
2. 您想要的3的数量应该是满足约束的最小数量，因为这样您就会有更多的5，从而获得更大的数量
3. 3的个数必须可以被5整除。这意味着，任何一点的3s都不超过10个：你应该只考虑0、5或10个3s。这是因为你想要最小的数字，使剩余的数字可以被3整除，以满足其他约束。如果具有15个3秒是有效的，那么具有0个3秒也是有效的；如果20起作用，那么5起作用；如果25有效，那么10也有效。一般来说，从3的数量中减去15将使约束条件仍然得到满足（如果它们以前是这样的话）
4. 因此，5s的个数必须是n-0、n-5或n-10，我们想要一个能被3整除的数。如果n已经被3整除，计算c = 5*(2*n%3)将给你0个3秒，因此n 5秒；如果n大于3的倍数1，则10个3秒，因此n-10个5秒，在这种情况下，n-10仍然可以被3整除；等等
5. 唯一需要测试的是c3s和n-c5s的计算是否满足n-c应该是非负的隐含约束。如果它是否定的，那么就没有解决方案；如果它是非负的，那么这是一个有效的解决方案，并且前加载5s将为您提供最大的此类解决方案

这是一类相当广泛的"编程"问题之一，在这些问题中，测试并不是真正看你是否能写出一些能完成任务的代码，而是看你是否能够从逻辑上把问题简化到琐碎的程度，并且可以非常有效地解决。

Answer 3

我认为数学有点帮助，我阅读了它的不同部分和历史。我的解决方案第一次通过了所有15项测试，所以虽然我没有使用数学，但我对此的看法可能会对你有所帮助。我处理了10个及以下的边缘情况，我只是硬编码。只要超过10，我就除以3，得到最多的555。当然，当除以3时，余数只能是0、1或2。零当然意味着不管写多少次555。一种方法是减去555中的3个，回到10个三分球的10个空位。两个意味着减去555中的1，从而为33333留下5个时隙。

剩下的3个如果。边缘情况为10个if。如果是约束条件，则为1。1用于。

Answer 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的倍数。

模0意味着可整除数模1意味着5需要减去两次。模2意味着需要减去5一次。