#C. 调虎离山

    传统题 文件IO:diao 1000ms 256MiB

调虎离山

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

待天以困之,用人以诱之,往蹇来返。

题目描述

33DAI 承包了一座“满二叉树”山,山上一共有 2m12^m-1 个山洞,山洞编号从 12m11\sim 2^m-1

33DAI 在山上养了 nn 只老虎,已知第 ii 只老虎目前在编号为 aia_i 的山洞里。

山洞之间有道路相连,每条道路连接两个山洞,老虎可以在一秒钟之内通过道路从其中一个山洞转移到另一个山洞。山洞和道路都无限大,道路可以同时容纳无限老虎通行,山洞也可以容纳无限老虎。编号为 ii 的山洞会和编号 i2, i2, i2+1\lfloor\frac{i}{2}\rfloor,\ i*2,\ i*2+1 的山洞之间各有一条道路(如果编号不在 12m11\sim 2^m-1 之内则没有那个山洞也没有那条道路)。

现在 33DAI 想把所有老虎调到编号为 2m12^m-1 的山洞中,每只老虎都会沿着最快的路径抵达,请你算算最晚到达的老虎需要多长时间能到达。

输入格式

第一行两个数 n,mn,m

第二行为 nn 个整数:a1ana_1\sim a_n

输出格式

一个数,即最晚到达的老虎多长时间能到达。

3 4
11 6 7
6

如上图,1111 号山洞的老虎距离 241=152^4-1=15 号山洞最远,要花 66 分钟。

3 4
2 13 14
4

2213131515 都需要 44 分钟。

数据规模与约定

对于 100%100\% 的数据,1n1051 \le n \le 10^51m631\le m\le 631ai2m11\le a_i\le 2^m-1

  • 子任务 1(10 分):保证 n=1n=1
  • 子任务 2(20 分):保证 ai+1a_i + 1 是某个 22 的整数次幂,即存在 xx 使得 ai+1=2xa_i+1=2^x
  • 子任务 3(30 分):保证 m=20m=20
  • 子任务 4(40 分):没有特殊限制。

挖土机 CSP-J 模拟赛 ~ 第十场

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-10-3 4:00
结束于
2024-10-5 4:00
持续时间
3.5 小时
主持人
参赛人数
88