C. Penchick and BBQ Buns （python解）-codeforces

原题链接：

点击传送

问题分析：

我们需要为给定数量的 BBQ 包子分配填料，满足以下条件：

1. 每种填料必须至少使用两次，或者不使用。
2. 任何两个相同填料的包子之间的距离必须是一个完全平方数。

思路:

• 为了满足条件，我们可以利用完全平方数的特性。完全平方数是指可以表示为某个整数的平方的数，前几个完全平方数为：1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, ...

代码：

​

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        if n <= 25 and n % 2 != 0:
            print("-1")
        elif n % 2 != 0 and n >= 27:
            print("1 2 2 3 3 4 4 5 5 1 6 6 7 7 8 8 9 9 10 10 11 11 12 13 13 1 12", end=' ')
            if n > 27:
                r = 14
                for i in range(28, n, 2):
                    print(r, r, end=' ')
                    r += 1
        else:
            r = 1
            for i in range(1, n + 1, 2):
                print(r, r, end=' ')
                r += 1
        print()
if __name__ == "__main__":
    main()