Problem Solution

1 solutions

  • 0
    @ 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
178
Accepted
31
Accepted Ratio
17%
Uploaded By