【uoj#282】长度测量鸡 结论题
给出一个长度为 $\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;
}
最新文章
- Validate US Telephone Numbers
- 分析sql语句所有表名及其别名的正则表达式
- 深入体验bash on windows,在windows上搭建原生的linux开发环境,酷!
- 编程语言 IDE 对比
- virtualbox下 ubuntu 14.04设置外网独立IP
- Python操作MySQL之SQLAlchemy
- jQuery插件综合应用(一)注册
- G - Island Transport - hdu 4280(最大流)
- MySQL--query-cache
- 用c++开发基于tcp协议的文件上传功能
- MVC中发生System.Data.Entity.Validation.DbEntityValidationException验证异常的解决方法
- Memcached【第二篇】高可用集群搭建
- ssh 设置私钥实现两台linux主机无密码访问
- Kubernetes 笔记 04 架构是个好东西
- java基础(十四)-----详解匿名内部类——Java高级开发必须懂的
- django第一天
- python函数解释
- ajax接口和后台交互
- Haskell语言学习笔记(72)Free Monad
- javaweb 学习系列【转】