534B.md (1988B)
1 Source: https://codeforces.com/problemset/problem/534/B 2 3 B. Covered Path 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 The on-board computer on Polycarp's car measured that the car speed at the beginning of some section of the path equals *v*1 meters per second, and in the end it is *v*2 meters per second. We know that this section of the route took exactly *t* seconds to pass. 22 23 Assuming that at each of the seconds the speed is constant, and between seconds the speed can change at most by *d* meters per second in absolute value (i.e., the difference in the speed of any two adjacent seconds does not exceed *d* in absolute value), find the maximum possible length of the path section in meters. 24 25 Input 26 27 The first line contains two integers *v*1 and *v*2 (1 ≤ *v*1, *v*2 ≤ 100) — the speeds in meters per second at the beginning of the segment and at the end of the segment, respectively. 28 29 The second line contains two integers *t* (2 ≤ *t* ≤ 100) — the time when the car moves along the segment in seconds, *d* (0 ≤ *d* ≤ 10) — the maximum value of the speed change between adjacent seconds. 30 31 It is guaranteed that there is a way to complete the segment so that: 32 33 * the speed in the first second equals *v*1, 34 * the speed in the last second equals *v*2, 35 * the absolute value of difference of speeds between any two adjacent seconds doesn't exceed *d*. 36 37 Output 38 39 Print the maximum possible length of the path segment in meters. 40 41 Examples 42 43 Input 44 45 ``` 46 5 6 47 4 2 48 ``` 49 50 Output 51 52 ``` 53 26 54 ``` 55 56 Input 57 58 ``` 59 10 10 60 10 0 61 ``` 62 63 Output 64 65 ``` 66 100 67 ``` 68 69 Note 70 71 In the first sample the sequence of speeds of Polycarpus' car can look as follows: 5, 7, 8, 6. Thus, the total path is 5 + 7 + 8 + 6 = 26 meters. 72 73 In the second sample, as *d* = 0, the car covers the whole segment at constant speed *v* = 10. In *t* = 10 seconds it covers the distance of 100 meters.