Codeforces Round #224 Div.2 Problem.B--Number Busters

  原题如下：

B. Number Busters

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Arthur and Alexander are number busters. Today they've got a competition.

Arthur took a group of four integers a, b, w, x (0 ≤ b < w, 0 < x < w) and Alexander took integer с. Arthur and Alexander use distinct approaches to number bustings. Alexander is just a regular guy. Each second, he subtracts one from his number. In other words, he performs the assignment: c = c - 1. Arthur is a sophisticated guy. Each second Arthur performs a complex operation, described as follows: if b ≥ x, perform the assignment b = b - x, if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b).

You've got numbers a, b, w, x, c. Determine when Alexander gets ahead of Arthur if both guys start performing the operations at the same time. Assume that Alexander got ahead of Arthur if c ≤ a.

Input

The first line contains integers a, b, w, x, c (1 ≤ a ≤ 2·10⁹, 1 ≤ w ≤ 1000, 0 ≤ b < w, 0 < x < w, 1 ≤ c ≤ 2·10⁹).

Output

Print a single integer — the minimum time in seconds Alexander needs to get ahead of Arthur. You can prove that the described situation always occurs within the problem's limits.

 

  这道题的来历在题目有中已经说明了。初看这道题觉得蛮简单的。就是模拟两人的计算过程，其中有个小小的分类讨论。啪啪啪迅速代码实现之后还稳稳地把给出来的数据都测试了一遍，都通过了。于是立马提交。可是在第五个测试数据的时候超时了！这才回过头来仔细想，如果a，c的数据给的过于极端（a = 1, c = pow(10, 9)*2 的话，就要计算超过pow(10, 9)*2次，这显然超时了！也就是说，这个题目有更加简单的算法，这个算法的首要条件是不可对计算过程进行模拟！

  于是，我改变思路，去求解模拟计算次数n的数学表达式。得到n >= ((c-a) * w - b) / (w-x);这个式子。

  后来，在提交失败后，又找到了这个式子的限制条件，n > 0。并且解决了将整型数据向上取的问题。才把这个小题给AC了。

  从此题得到的经验是：1、小题目有大技巧（直接找关于答案n的数学表达式）

                                      2、得到数学表达式后不要大喜过望，直接提交，要找找其限制条件，否则就要看到大红的WA!

                                     3、下次遇到这种题目首先要考虑的是应该用什么样类型的算法，将不可能的算法排除掉（本次如果模拟计算过程的话，遇到极端数据绝对超时，不能保证该算法的正确性）

  下面附上本人代码。

#include<stdio.h>
#include<stdlib.h>
main()
{
	__int64 a, c;
	double b, w, x;
	scanf("%I64d%lf%lf%lf%I64d", &a, &b, &w, &x, &c);
	long long n;
	double p;
	if(a < c){
		p = ((c-a) * w - b) / (w-x);	
		n = p;
		double d = p - n;
		if(d > 0)
			n += 1;
	}		
		else
		n = 0;
	printf("%I64d\n", n);	
}