首页 > 代码库 > Codeforces Round #224 (Div. 2) B 数学推理
Codeforces Round #224 (Div. 2) B 数学推理
挺有意思的一道题目,一开始发现了循环节,做了一下,发现许多小地方要补,比较繁琐,做了几个小时的无用功吧,但是循环节肯定可以只是我写搓了,后来又推了公式,发现可以的
首先当b<x的时候,c--,a--那么对于 a,c来说他们之间的差并没有减小,所以真正起到作用的是b>=x的时候,这个时候只有c--,但是答案要求的 是多少次,在b<x的时候 是要经过一定次数的 w-(x - b)来重新使得b>=x,所以第二部分对答案有影响,但是 设方程的话 就不需要多设一个未知数,因为 第一部分肯定 是要进行(c - a)次才行
推一下b<x的时候
第一步: b1 = w - (x - b) = w - x + b,然后判断b1是否还是小于x,若还是继续第二步
第二步:b2 = w - (x - b1) = w - (x - (w - (x - b))) = 2 * w - 2 * x + b,然后判断同上
第三步:b3 = w - (x - b2) = 3 * w - 2 * x + b
然后你就会发现,其实在b<x的时候 对于b每一次的增长的值 为(w - x)
然后我们开始列方程,设 b<x的时候进行了k次,那么b的增长值为 (w - x) * k
然后我们列出 还剩最后一步就能使得 c<=a 的方程,也就是 c - a = 1的时候的方程
b - x * (c - a - 1) + (w - x) * k >= x
前面部分很好理解,因为每一步具体要怎么处理a,c,是要看b的值来决定的,所以我们列方程左边就是跟b有关的值
b - x * (c - a - 1)的意思呢,就是我花了 (c - a - 1)次使得 a,c的差值减少到 为1,那么我每这样一次 b的值都要减去x,
+ (w - x) * k的意思就是 因为b有小于x的时候,我假设在b<x的时候 进总共行了k次操作来使得b又大于等于x
至于左边式子为何要>=x,因为 这个方程实在 c - a = 1的时候的方程,也就是说 下一个状态我要求 c == a,所以至少我当前的b的值要>=x这样我下一步才能够 进入b>=x的这个环节 从而使得c--,然后 使得c<=a这样就结束了
推完过了以后看了别人的,推出的式子跟他们的一样,但是说法不一样,没理解他们的想法,我觉得我这个渣渣相出的思路肯定是易懂的
只给出了代码 没给出头文件
ll aa,bb,w,x,cc; ll ans = 0; void init() { } bool input() { while(cin>>aa>>bb>>w>>x>>cc) { return false; } return true; } void cal() { ans = 0ll; if(cc <= aa)return ; ll k = ceil(((cc - aa) * x - bb) * 1.0/(w - x) * 1.0); ans = k + cc - aa; } void output() { cout<<ans<<endl; } int main () { while(true) { init(); if(input())return 0; cal(); output(); } } /* 1 0 1000 999 2000000000 10 3 6 5 30 10 3 5 1 30 10 32 312 72 1000 117 25 1287 */