HDOJ 5417-Victor and Machine Victor and Machine Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 177 Accepted Submission(s): 91 Problem Description Victor has a machine. When the machine starts up, it will pop out a ball immediately. After that, the machine will pop out a ball every w seconds. However, the machine has some flaws, every time after x seconds of process the machine has to turn off for y seconds for maintenance work. At the second the machine will be shut down, it may pop out a ball. And while it’s off, the machine will pop out no ball before the machine restart. Now, at the 0 second, the machine opens for the first time. Victor wants to know when the n-th ball will be popped out. Could you tell him? Input The input contains several test cases, at most 100 cases. Each line has four integers x, y, w and n. Their meanings are shown above。 1≤x,y,w,n≤100. Output For each test case, you should output a line contains a number indicates the time when the n-th ball will be popped out. Sample Input 2 3 3 3 98 76 54 32 10 9 8 100 Sample Output 10 2664 939 Source BestCoder Round #52 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5421 5420 5419 5418 5416
有两种解法，一模拟，二推导公式。我采用的是第二种方法，根据x和w的大小关系，分为3种情况。 当w>x时，只可能启动的时候弹出小球，相邻两球弹出的时间间隔为x+y，因为0时刻会弹出一个球，所以总时间为(n-1)*(x+y)。 当w==x时，每隔(x+y)弹出2球，如果n为奇数，n-1为偶数，则需要花(n-1)/2*(x+y)时间，这里n-1减去了0时刻那个球，因为那个球不花时间；如果n为偶数，n-1为奇数，代入上式为(n-2)/2*(x+y)，但是这里的n-1减去了一个球，最后还要隔x时间才弹出一个球，所以还需加上x，即(n-2)/2*(x+y)+x。 当w<x时，每x+y时间会弹出num=x/w+1个球，如果n不能整除num，则n/num是int型，即有n/num个完整的周期，还剩下n%num个球没弹出来，因为每个w时间弹一个球，所以只需间隔n%num-1次就可弹出n%num个球，总时间为(n/num)*(x+y)+(n%num-1)*w；如果n能整除num，则有n/num个完整的周期，我们先算前n/num-1个周期，时间为(n/num-1)*(x+y)，最后一个周期，因为机器开启时刻会弹出一个球，所以只需间隔num-1次即可弹出这个周期剩余的球，加上w*(num-1)。 完整代码如下： [cpp] #include<iostream> #include<cstdio> using namespace std; int main() { int x, y, w, n; while (scanf("%d %d %d %d", &x, &y, &w, &n) != EOF) { if (w > x) printf("%d\n", (n – 1)*(x + y)); else if (w == x) { if (n & 1) printf("%d\n", ((n – 1) / 2)*(x + y)); else printf("%d\n", ((n – 2) / 2)*(x + y) + x); } else { int num = x / w + 1; if (n % num == 0) printf("%d\n", (n / num – 1)*(x + y) + w * (num – 1)); else printf("%d\n", (n / num)*(x + y) + (n % num – 1) * w); } } return 0; } [/cpp] 本代码提交AC，用时0MS，内存1560K。]]>