牛客-像鱼题解

像鱼

题意：给你一个边长为 n 的用硬币摆成的实心三角形，请问把他倒过来最少需要多少步？

题解：本来像随便来偷一题玩玩，结果发现不会做😱，后来知道能oeis O(1)做🧐， 规律就是1, 1, 1, 2, 2, 2, 3, 3, 3

除了oeis也能自己推，考虑保留某一行，那么倒三角能保留地点就是某一行之上的所有和某一行为基础尽量向下的三角形(梯形)

设最底行为0，设行数为x，每次能保留的硬币为y，易得到\(y=2*(x+1)\frac{(n-x)+(n-x-x)}{2}-(n-x)\)

答案为\(\frac{n*(n+1)}{2}-y\), 通项之后发现是二元一次方程，取最大值时\(x=\frac{-b}{2a}\)

当x不为整数时\(\lfloor x \rfloor , \lceil x \rceil\)均有可能，取min即可

1
2
3
4
5
6
7

mod = 23333333333333333
for _ in range(int(input())) :
    n = int(input())
    x1 = (2 * n - 2 + 5) // 6
    x2 = x1 - 1
    print((n * (n + 1) // 2 - max((-3 * x1 * x1 + (2 * n - 2) * x1 + n), 
    (-3 * x2 * x2 + (2 * n - 2) * x2 + n))) % mod)