MinimizeAbsoluteDifferenceDiv2

SRM 733 · 2018-04-13 · by ltdtl

SRM 733 · 2018-04-13 · by ltdtl · Brute Force, Simple Math

Show categories

Class Name: MinimizeAbsoluteDifferenceDiv2

Return Type: int[]

Method Name: findTriple

Arg Types: (int, int, int)

Problem Statement

You are given three positive integers: the ints x₀, x₁, and x₂. You have the following expression: |(?/?) - ?|. You want to replace the three question marks with your three integers in some order. In what order should you place the three integers if your goal is to make the result as small as possible?

More formally, you have an expression of the form | (x_a / x_b) - x_c |. Here, "/" denotes real division (e.g., 7/2 = 3.5), and "||" denotes absolute value. Your task is to choose three distinct subscripts a, b, c so that the value of the expression is as small as possible.

Return a int[] with three elements: the optimal values {a, b, c}. If there are multiple optimal answers, you may return any of them.

Constraints

x0 will be between 1 and 10,000, inclusive.
x1 will be between 1 and 10,000, inclusive.
x2 will be between 1 and 10,000, inclusive.

Examples

1
1
1
Returns: {0, 1, 2 }

Regardless of our choice of subscripts, the expression is always evaluated to |(1/1) - 1| = 0. Any of the six permutations of {0, 1, 2} is a correct answer.

1
2
3
Returns: {1, 2, 0 }

The return value {1, 2, 0} corresponds to the expression |(x1 / x2) - x0| = |2/3 - 1| = 1/3 = 0.333333. This is the only optimal choice of {a, b, c}, all other choices produce expressions with a larger value.

7
20
5
Returns: {1, 0, 2 }

This set of subscripts produces an expression with the value 15/7.

6
2
3
Returns: {0, 1, 2 }

There are two correct answers: {0, 1, 2} and {0, 2, 1}. You may return either of them.

10
11
111
Returns: {2, 1, 0 }

Submissions are judged against all 159 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MinimizeAbsoluteDifferenceDiv2 with a public method vector<int> findTriple(int x0, int x1, int x2) · 159 test cases · 2 s / 256 MB per case