2019牛客国庆集训派对day3 时间旅行(思维)

LINK

现在$Bob$在数轴点 t 0 t_0 t0​,要回到 [ 0 , h 0 ] [0,h_0] [0,h0​]中

当处于数轴上$t$点时,可以选择一个$x$满足 ⌈ x h ⌉ ∗ h < = c \lceil \frac{x}{h} \rceil*h<=c ⌈hx​⌉∗h<=c

时间机器会在$[0,x]$随机选择一个数$y$回到$t-y$处,同时燃料变成$c-y$

现在为了保证能回到 [ 0 , h 0 ] [0,h_0] [0,h0​],求出最大的距离$T$

可以想象,如果点$k$无法回到 [ 0 , h 0 ] [0,h_0] [0,h0​],那么$k$以后的点也必然不能

因为时间机器是完全随机的,那么可以假定最坏情况,每次走$1$步

那么就要求 [ h 0 + 1 , k − 1 ] [h_0+1,k-1] [h0​+1,k−1]都是完全保证能回到 [ 0 , h 0 ] [0,h_0] [0,h0​]的

我们再看看这个式子 ⌈ x h ⌉ ∗ h < = c \lceil \frac{x}{h} \rceil*h<=c ⌈hx​⌉∗h<=c

进一步可以得到$x$的取值范围是$[0,c-c\%h]$

换句话说,当$c<h$时,$x$取值范围永远是$0$,走不动,所以无法回到 [ 0 , h 0 ] [0,h_0] [0,h0​]

那么当$c>h$呢??因为时间机器的随机性,我们不管怎么选$x$

设起点为$f$,那么途径的点是 f − 1 , f − 2 , f − 3... h 0 f-1,f-2,f-3...h_0 f−1,f−2,f−3...h0​

这也要求期间每个位置的$c$都要大于 h 0 h_0 h0​

其实答案就是$c-1$了

#include
using namespace std;
int h,c;
int main()
{while( cin >> h >> c ){if( c<h )	cout << h;else	cout << c+1;cout << endl;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！