#U1516JB2. Angry Cows
Angry Cows
Bessie the cow 设计了她认为会成为下一个热门电子游戏:“愤怒的奶牛”。她认为完全原创的前提是玩家用弹弓将一头奶牛射入一维场景,该场景由一组位于数轴上不同点的干草捆组成。奶牛以足够的力量落在干草捆上,导致草捆爆炸,这反过来可能引发连锁反应,导致附近的其他干草捆爆炸。目标是使用一头奶牛引发连锁反应,引爆尽可能多的干草捆。
有 N 个干草捆位于不同的整数位置 在数轴上。如果一头牛被发射到位置 x 的干草捆上,这个干草捆会以 1 的“爆炸半径”爆炸,这意味着 1 单位距离内的任何其他干草捆也会被爆炸吞没。然后这些相邻的大包会自行爆炸(同时发生),每个爆炸半径为 2,因此这些爆炸可能会吞噬最多 2 个单位距离以外的其他尚未爆炸的大包。在下一个时间里,这些草捆也以爆炸半径 3 爆炸(全部同时)。一般来说,在时间 t,一组干草捆将爆炸,每个干草捆的爆炸半径为 t。被这些爆炸吞没的捆包本身将在时间 t+1 爆炸,爆炸半径为 t+1,以此类推。
如果将一头奶牛发射到最好的干草捆上以开始连锁反应,请确定最大的干草捆数量。
输入格式(文件anger.in):
输入的第一行包含 N (1≤N≤100)。剩下的 N 行都包含整数 …(每个都在 0…1,000,000,000 范围内)。
输出格式(文件anger.out):
请输出一头牛可以引起爆炸的最大干草捆数。
样例输入:
6
8
5
6
13
3
4
样例输出:
5
在此示例中,将一头奶牛发射到位置 5 的干草捆上会导致位置 4 和 6 的草捆爆炸,每个草捆的爆炸半径为 2。这些爆炸反过来又导致位置 3 和 8 的草捆爆炸,每个草捆都带有爆炸半径 3。但是,这些最终爆炸的强度不足以到达位置 13 的草捆。