Satisfaction Score
Time limit2sMemory limit512 MB
Split 8 skill scores into two doubles games and re-pair each game's four players into teams to maximize the minimum satisfaction over all members.
- Level
Medium6 of 10
- Topics
- Brute force, Implementation, Sorting
- Solved
- No attempts yet
Problem
The president of a tennis club must form 2-versus-2 doubles pairings each week so that the participating members are satisfied. A member is more satisfied the more evenly matched the games they play in are. Assuming the skill scores of the participating members are given as integers between 0 and 10 inclusive, the satisfaction score of a member who plays in a game is expressed as follows.
1 - ( |average skill score of the opposing team - average skill score of their own team| / 10)
This score ranges from 0 in the worst case to 1 in the best case.
The president's goal is to ensure that no member quits out of excessive dissatisfaction. To this end, the president wants every member to play at least once and wants to maximize the lower bound of the satisfaction scores.
Suppose 2 tennis courts are available, exactly one game can be played on each court, and 8 members participate. Write a program that finds the lower bound of the satisfaction scores when the pairings are formed to meet this goal.
Input
The skill scores of the 8 members are given as input. The scores are separated by spaces.
Output
Print the lower bound of the satisfaction scores on the first line.
If the answer can be expressed as an integer or a real number with one decimal place, print it to one decimal place; if it can be expressed with two decimal places, print it to two decimal places.