1 solutions
-
0thakuremon LV 4 @ 2024-07-15 13:15:10
let assume A <= B <= C and we are going to make A=B=C=P
suppose, P = B + x where , x is an arbitrary number (positive or negative)
to make B=P we need to add {x ... (1)} with B
then, K must be a divisor of x.to make A=P we need to add {B+x-A = (B-A)+x ..... (2)} with A
then, K must be a divisor of (B-A)+x
since K divides x, then K will also divide (B-A) .... (i)to make C=P we need to subtract {A-(B+x) = (C-B)-x .... (3)} from C
then, K must be a divisor of (C-B)-x
since K divides x, then K will also divide (C-B) .... (j)so the total distance to be covered is :
(1)+(2)+3
= x+(B-A)+x+(C-B)-x
= C-A+x
= c-B+B-A+x [add and subtract B]
= (C-B)+(B-A)+x ......(4)we need to take the mininum value of x (must be a multiple of K) such that K divides equation (4)
from (i)(j) we know that K divides (B-A) and (C-B)
so if we take x=0 (lowest multiple of any K) the equation (4) will also be divided by K
and the optimal value of K will be the GCD of (B-A) and (C-B)as a result it is proved that the optimal P is :
P = B + x = B (x=0)
so, K = GCD(B-A , C-B)
ans = (B-A)/k + (C-B)/k
= (B-A+C-B)/K
= (C-A)/K
- 1
Information
- ID
- 1061
- Difficulty
- 7
- Category
- Beginners Click to Show
- Tags
- # Submissions
- 181
- Accepted
- 36
- Accepted Ratio
- 20%
- Uploaded By