当前位置: 首页 > news >正文

IMO2025 Problem 1

image

考虑 \(n = 3\) 时的下三角,显然有三个容易构造的解,\(k = \{0, \, 1, \, 3\}\),构造如下:

image

image

image

那么 \(n > 3\) 呢?由于下三角的点数恰好为 \(1 + 2 + \cdots + n\) 个点,对于第一条直线,有且仅有 \(3\) 中方式覆盖 \(n\) 个点,也就是非 sunny 的直线,这条直线画完之后将会把下三角递归到第 \(n - 1\) 层,因此同解。

考虑证明不存在其他解,如果考虑不进行递归,那么三角形的三个顶点分别对应三条直线,而边上共有 \(3\)故下三角的斜边上 \(n\) 个点每一个点对应一条 sunny 直线,如果需要覆盖掉直角边上的 \(3n - 3\) 个点,至少需要 \(\left\lceil\frac{3n - 3}{2}\right\rceil \ge n\),当且仅当 \(n = 3\) 时等号成立,故不存在其他方案。

因此符合题目条件的所有的 \(k \in \{0, \, 1, \, 3\}\)

http://www.gsyq.cn/news/33271.html

相关文章:

  • Java流程控制——switch多选择结构
  • P3607 [USACO17JAN] Subsequence Reversal P 题解
  • 随笔/杂记
  • 使用 Swift 解析验证码(结合 Tesseract OCR)
  • 常见排序算法Java实现
  • 175天 隧道技术篇防火墙组策略FRPNPSChiselSocks代理端口映射C2上线
  • link元素的用法及HTML样板
  • 10月28号
  • https://avoid.overfit.cn/post/44c8d547475340d59aa4480f634ea67f
  • Day 18
  • STM32之fromelf生成bin和反汇编文件
  • 常用存储器介绍
  • P11307 [COTS 2016] 建造费 Pristojba 分析
  • 乱学点东西#2 :菠萝/蓝莓/Boruvka算法
  • 文件清理,推荐几款常用软件
  • 【学习笔记】数据结构全家桶
  • 零散点小总结(25.10.28)
  • Top Tree大学习
  • EVE-NG导入华为等镜像的方法
  • 2025 云斗
  • c++ ranges随笔
  • P10259 [COCI 2023/2024 #5] Piratski kod
  • 软考复习总结
  • ? #6
  • 集训做题杂记1 - -MornStar
  • 2019 福建省队集训录
  • 实验二 现代C++编程初体验
  • ZKY精选冲刺省选国赛仿真训练题
  • MySQL 查询与更新语句执行过程深度解析:从原理到实践​ - 指南
  • ZKY精选冲刺省选国赛技巧训练题