首页 > 代码库 > 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

*/