Problem Statement |
| | You are the problem coordinator of a programming contest. You have an archive of problems from which you must choose three distinct problems - one easy, one medium and one hard. Each problem has a difficulty level that is given as an integer. The higher the difficulty level, the harder the problem is to solve. The medium must be at least as difficult as the easy, and the hard must be at least as difficult as the medium. You want the difference in difficulty between the easy and medium to be as close as possible to the difference between the medium and the hard. This means that if E, M and H are the difficulties of the easy, medium and hard problems, respectively, then you want to minimize |D1 - D2|, where D1 = M - E and D2 = H - M. If there are multiple ways to achieve this, choose the one among them with the easiest easy. If there are still multiple ways remaining, choose the one among them with the hardest hard. Finally, if there are still multiple ways remaining, choose the one among them with the easiest medium. You are given a int[] difficulties, each element of which is the difficulty level of a problem in the archive. Return a int[] containing exactly three elements - the difficulty levels of the easy, medium and hard problems you choose, in order. |
| |
Definition |
| | | Class: | ProblemSetter | | Method: | chooseProblems | | Parameters: | int[] | | Returns: | int[] | | Method signature: | int[] chooseProblems(int[] difficulties) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | difficulties will contain between 3 and 50 elements, inclusive. |
| - | Each element of difficulties will be between 1 and 1000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: {1, 3, 5 } | | If we choose the problem with difficulty 1 as the easy, difficulty 3 as the medium, and difficulty 5 as the hard, then the difference between the easy and medium is exactly the same as the difference between the medium and hard. We can achieve the same effect by choosing difficulties 2, 3 and 4, but we prefer the selection with the easier easy problem. |
|
|
| 1) | |
| | |
| 2) | |
| | { 10, 3, 4, 7, 8, 9, 3, 7, 7, 9 } |
| Returns: {4, 7, 10 } | | Note that the input will not necessarily be given in sorted order. |
|
|
| 3) | |
| | | Returns: {1, 104, 210 } | | Two solutions {1, 4, 10} and {1, 104, 210} have the same |D1 - D2| and the same easy. {1, 104, 210} is preferred because it has a more difficult hard. |
|
|
| 4) | |
| | | Returns: {1, 5, 10 } | | Two solutions {1, 5, 10} and {1, 6, 10} have the same |D1 - D2| and the same easy and hard. {1, 5, 10} is preferred because it has an easier medium. |
|
|
| 5) | |
| | | Returns: {5, 5, 5 } | | Note that the easy can be of the same difficulty as the medium, and the medium can be of the same difficulty as the hard. |
|
|
| 6) | |
| | { 77, 331, 39, 551, 408, 904, 959, 544, 107, 515 } |
| Returns: {107, 331, 551 } | |
|