小沙跳悬崖,经典咏流传(easy version)

发布时间:2024年01月06日

本题有对应的hard version,区别仅在数据范围,保证easy version的测试用例集是hard version的真子集,通过困难版本的代码可直接通过简单版本。

小沙学会了影分身之术,他和他的分身们一共101810^{18}1018只小沙现在使用钩爪固定在一个随时间逐渐合拢的悬崖两侧,如果小沙能说出悬崖两侧的距离,那么悬崖就会停止合拢,否则悬崖就会把这群小沙挤死。


具体来讲,一开始小沙们知道的信息为:悬崖两侧的距离不小于lll且不大于rrr。

接下来每个时刻按照顺序依次进行如下操作。

1、询问小沙们是否知道悬崖两侧的距离,若小沙不知道则不能进行回答(小沙不能猜一个答案,你可以认为一旦小沙猜错,悬崖会立刻以光速合拢,压死所有小沙),若小沙们此时知道答案,悬崖立即停止合拢,剩余的小沙全部存活。

2、小沙们选择一只小沙从悬崖的一侧跳向另一侧,且弹跳的距离为xxx,小沙可以自己任意选择xxx的值,若悬崖两侧的距离大于xxx,则这只小沙会摔死,否则这只小沙还活着,还可以进行下一次弹跳。

3、悬崖合拢111个单位,若合拢后悬崖两侧的距离为000,则立即压死所有的小沙。

小沙必须在某一轮操作中进行“回答”并且正确才可以停止悬崖的合拢,并结束所有过程,而不是当他“知道”悬崖的答案时。

如果小沙的运气非常差,那么在最坏的可能下,小沙们使用最优策略,此时至少死亡多少只小沙?


对于第一个样例:

小沙在第一轮直接推理出当前悬崖的长度为111,所以没有小沙会被压死或者跳崖身亡。

对于第二个样例:

如果小沙选择第一轮令x=2x=2x=2这个长度跳崖,虽然此时小沙不会死,但是也没有得到任何有用的信息。

如果小沙选择第一轮令x=1x=1x=1这个长度跳崖,有两种情况,摔死了或者没摔死,如果没摔死,则说明当前悬崖长度就是111。但是由于第一轮在小沙跳崖后,悬崖的尺寸会合拢减少111,此时悬崖完全合并,没有下一轮再让小沙回答悬崖的长度了,导致所有的小沙都被压死了。题目要求“最坏情况”,所以答案为101810^{18}1018。

对于第三个样例:

具体情况同第二个样例,但是此时由于悬崖合拢111个单位后也不会压死所有小沙,所以至多摔死一个小沙,然后小沙在下一轮回答悬崖的长度,然后结束。

对于第四个样例:

如果小沙第一轮不选择令x=2x=2x=2这个长度跳崖,那么接下来的最坏情况都将导致所有小沙都被压死。类似的,接下来的任意轮中,小沙都会选择x=2x=2x=2这个长度跳崖。

文章来源:https://blog.csdn.net/tesla_shy/article/details/135422843
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。