找到"体面"数字算法推理？

Question

问题

夏洛克·福尔摩斯对他的大敌莫里亚蒂教授感到十分偏执.他所有压制Moriarty的努力都是徒劳的.这些天Sherlock正在研究Watson博士的一个问题.沃森提到中情局最近一直面临着超级计算机"野兽"的奇怪问题.

今天下午,Sherlock收到了Moriarty的一张纸条,说他用病毒感染了"野兽".此外,纸币上印有数字N. 经过一些计算,Sherlock发现消除病毒的关键是拥有N位数字的最大"体面"数字.

"体面"号码有 -

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

与此同时,对"野兽"的破坏反击速度非常快.你可以保存'The Beast',并在Sherlock之前找到钥匙吗？

输入格式第1行将包含整数T,即测试用例的数量.接下来是T行,每行包含一个整数N,即数字中的位数

输出格式最大有N位的体面数.如果不存在这样的号码,请告诉Sherlock他错了并打印'-1'

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

样本输入

4
1
3
5
11

样本输出

-1
555
33333
55555533333

说明对于N = 1,没有这样的数字.

对于N = 3,555只是可能的数字.

对于N = 5,333333仅是可能的数字.

对于N = 11,55553333333并且所有数字排列都是有效数字,其中,给定数字是最大数字.

回答

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是3 FROM N的下一个倍数相同.

例如,如果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,1 ......,以及作者选择的原因这个特殊的表达方式,我不能说.

您还可以考虑N%3在这个意义上是如何接近N的下一个LOWER倍数为3.