【uoj#282】长度测量鸡 结论题

时间：2022-01-07 00:50:21

题目描述

给出一个长度为 $\frac{n(n+1)}2$ 的直尺，要在 $0$ 和 $\frac{n(n+1)}2$ 之间选择 $n-1$ 个刻度，使得 $1\sim \frac{n(n+1)}2$ 中任意一个长度都可以由某两个刻度（包括 $0$ 和 $\frac{n(n+1)}2$ ）之间的距离表示出来。问是否有解。

$n\le 2500$

题解

结论题

结论：当且仅当 $n\le 3$ 时有解。

神TM结论。。。

证明：

由于只有 $C_{n+1}^2=\frac{n(n+1)}2$ 种选择，因此一个长度只能用一种方式表示。
当 $n>3$ 时，设 $m=\frac{n(n+2)}2$ ，有 $m\le 10$ 。
由于要表示 $m-1$ ，因此 $1$ 或 $m-1$ 必有刻度，由于对称性不妨设 $1$ 处有刻度。这样 $1$ 也被表示出来。
由于要表示 $m-2$ ，因此 $2$ 、$m-2$ 或 $m-1$ 必有刻度，而 $2$ 和 $m-1$ 会使得 $1$ 被表示两次，只能选择 $m-2$ 处。这样 $2$ 、$m-3$ 也被表示出来。
由于要表示 $m-4$ ，因此 $2$ 、$4$ 、$m-4$ 或 $m-3$ 必有刻度，而 $2$ 和 $m-3$ 会使得 $1$ 被表示两次，$m-4$ 会使得 $2$ 被表示两次，只能选择 $4$ 处。这样 $3$ 、$4$ 、$m-6$ 也被表示出来；
由于要表示 $m-5$ ，因此 $3$ 、$5$ 、$m-5$ 、$m-4$ 或 $m-1$必有刻度，容易发现这些位置都不能选择，无法表示 $m-5$ 。又因为 $m\le 10$ ，因此前面表示的 $1,2,3,4$ 均不等于 $m-5$ 。所以不能表示 $m-5$ ，无解，命题得证。

因此直接判断 $n$ 与 $3$ 的大小关系即可。

#include <cstdio>

int main()

{

    int T , n;

    scanf("%d" , &T);

    while(T -- ) scanf("%d" , &n) , puts(n > 3 ? "-1" : "1");

    return 0;

}

相关文章