Maximum times X and Y can be reduced to near 0 using numbers A or B | Helper function to check if we can perform Mid number of moves ; Remove atleast Mid * B from both X and Y ; If any value is negative return false . ; Calculate remaining values ; If val >= Mid then it is possible to perform this much moves ; else return false ; Initialize a variable to store the answer ; Fix the left and right range ; Binary Search over the answer ; Check for the middle value as the answer ; It is possible to perform this much moves ; Maximise the answer ; Return answer ; Driver Code ; Generalise that A >= B
MAXN = 10000000 NEW_LINE def can ( Mid , X , Y , A , B ) : NEW_LINE INDENT p1 = X - Mid * B NEW_LINE p2 = Y - Mid * B NEW_LINE if ( p1 < 0 or p2 < 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT k = A - B NEW_LINE if ( k == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT val = p1 // k + p2 // k NEW_LINE if ( val >= Mid ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def maxPossibleMoves ( X , Y , A , B ) : NEW_LINE INDENT ans = 0 NEW_LINE L = 1 NEW_LINE R = MAXN NEW_LINE while ( L <= R ) : NEW_LINE INDENT Mid = ( L + R ) // 2 NEW_LINE if ( can ( Mid , X , Y , A , B ) ) : NEW_LINE INDENT L = Mid + 1 NEW_LINE ans = max ( ans , Mid ) NEW_LINE DEDENT else : NEW_LINE INDENT R = Mid - 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT X = 10 NEW_LINE Y = 12 NEW_LINE A = 2 NEW_LINE B = 5 NEW_LINE if ( A < B ) : NEW_LINE INDENT tmp = A NEW_LINE A = B NEW_LINE B = tmp NEW_LINE DEDENT print ( maxPossibleMoves ( X , Y , A , B ) ) NEW_LINE