NIKKEI Programming Contest 2019-2 Task E. Non-triangular Triplets
必要条件
一方面
$\sum_{i=1}^{N}(a_i + b_i) \le \sum_{i=1}^{N} c_i \implies 2\sum_{i=1}^{N} c_i \ge \sum_{i=1}^{N}(a_i + b_i + c_i) = \sum_{i=K}^{K+3N-1} i = \frac{3N(2K+3N-1)}{2}$
另一方面
$\sum_{i=1}^{N} c_i \le \sum_{i=K+2N}^{K+3N-1} i = \frac{N(2K+5N-1)}{2}$
$N(2K+5N-1) \le \frac{3N(2K+3N-1)}{2} \implies 2K - 1\le N$
此必要条件也可用另一种方法推导出来:
由于 $\sum_{i = 1}^{N} (a_i + b_i) \ge \sum_{i=K}^{K+2N-1} i $ 且 $\sum_{i=1}^{N} c_i \le \sum_{i = K+2N}^{K+3N-1} i$,因此 $\sum_{i = 1}^{N} (a_i + b_i) \le \sum_{i=1}^{N} c_i \implies \sum_{i=K}^{K+2N-1} i \le \sum_{i = K+2N}^{K+3N-1} i \implies 2K - 1\le N$。
构造
the pattern is $(x, y)$, $(x+2, y -1)$, ...
例子
$K = 2, N = 6$
\begin{matrix}
3 & 5 & \enclose{right}{7} & 2 & 4 & 6 \\
10 & 9 & \enclose{right}{8} & 13 &12 & 11 \\
\hline
14 & 15 & 16 & 17 & 18 & 19
\end{matrix}
$K = 2, N = 7$
\begin{matrix}
2 & 4 & 6 & 8 & 3 & 5 & 7 \\
15 & 14 & 13 & 12 & 11 & 10 & 9 \\
\hline
19 & 20 & 21 & 22 & 16 & 17 & 18
\end{matrix}
最新文章
- uva 11609
- typedef和#define的区别
- hadoop入门必备基础知识
- A Tour of Go Multiple results
- Php GMP
- NET 项目结构搭建
- NewtonJson中转义的斜杠\和多余的引号处理
- 使用Core Animation对象来实现动画
- Jsoup使用教程
- springboot全局异常处理
- SPOJ 7258 Lexicographical Substring Search
- JVM垃圾回收总结
- ionic2中使用videogular2实现m3u8文件播放
- DeeplabV3+ 在自己环境下跑出现的错误
- Linux 指定运行时动态库路径【转】
- linux c生成唯一文件名称
- Android apk签名的两种方法
- 重要, 要播放音乐视频等多媒体: 安装fedora23中的多媒体编码器
- php中 isset函数有什么功能
- C - 无间道之并查集 HihoCoder - 1066
热门文章
- .NET(c#) 移动APP开发平台 - Smobiler(1)
- [JOI2012春季合宿]Constellation (凸包)
- Vue_(组件通讯)使用solt分发内容
- Vue_(组件通讯)非父子关系组件通信
- ansible主机互信
- linux命令---vi编辑器快速定位行数
- linux IP 网关配置
- c++ / % 四舍五入 向上取整ceil 向下取整floor
- 发布机制-A/B 测试:百科
- 学习 C++ 读什么书