#P18106. Jaded Juice
Jaded Juice
Jaded Juice
Lupa 有 个普通透明瓶和一个特殊透明瓶。普通瓶的高度都是 ,瓶底位于高度 ,瓶口位于高度 ;特殊瓶的高度为 。
最初,所有瓶子的果汁都达到同一个未知的整数高度 ,其中 。
第 个普通瓶的深色标签遮住高度从 到 的部分。因此,只有果汁高度严格小于 时,Lupa 才能看清这个瓶子的果汁高度。
特殊瓶的标签遮住高度从 到 的部分。因此,只有果汁高度严格大于 时,Lupa 才能看清特殊瓶的果汁高度。
一次操作中,Lupa 选择一个普通瓶和一个非负整数 ,从这个普通瓶向特殊瓶倒入恰好 单位的果汁。每次操作后,她会观察所有能看见的果汁高度。倒出或倒入 单位果汁,相应瓶子的果汁高度分别下降或上升 。
Lupa 不能执行可能无法完成的操作:在选择一次倒水前,考虑所有与此前观察结果相符的 。对于其中每一个可能的 ,被选的普通瓶里都必须至少有 单位的果汁,这次操作才合法。
她可以根据此前的观察结果调整之后的策略,并在能够唯一确定 时立即停止。最初不进行操作时,如果已有可见水位,也能直接确定 。
求最少需要多少次操作,才能保证无论初始隐藏高度 是多少,都能确定它。
输入格式
第一行包含两个整数 ,其中 ,。
第二行包含 个整数 ,其中 。
输出格式
输出一个整数,表示保证确定 所需的最少操作次数。
样例
输入:
3 34
1 2 4
输出:
3
样例解释
如果 ,初始时就能从标签为 的瓶子看到水位。否则,目前 。
先从标签为 的瓶子倒出 单位。若 ,普通瓶会露出水位;若 ,特殊瓶会露出水位。尚未确定的情况因此只剩 。
再从同一瓶倒出 单位。尚未确定的情况变为 。
最后从标签为 的瓶子倒出 单位。若 ,这个普通瓶露出水位;若 ,特殊瓶露出水位;否则只有 这一种可能。因此三次操作足够。