Максимальная разница очков между победителем и призером Турнира

Даны целые числа N и K , обозначающие количество команд, участвующих в футбольном турнире, где каждая команда играет только один матч с каждой другой командой, задача состоит в том, чтобы найти максимальную разницу в очках между победителем и занявшим второе место (второе место). турнира, в котором победитель матча получает K очков.

Примеры:

Input: N = 2, K = 4
Output: 4 
Explanation: If there are 2 team A and B then either A will win or loss.
If A wins the match it scores 4 points and team B score is 0.
Hence maximum possible difference of points between the winning team and the second-placed team is 4 .

Input: N = 3, K = 4
Output: 4

Input: N = 9, K = 5
Output: 20

Подход: задача может быть решена на основе следующего математического наблюдения:

The difference will be maximum when the winner wins all the matches it plays and all the other teams win near equal matches each. As each time is playing against others only once so the total number of matches is N * (N – 1)/2.

If the winner wins all matches (i.e.,  (N-1) matches that it plays) the remaining number of matches are:
(N * (N – 1))/2 – (N – 1) = (N – 1) * (N – 2) / 2.
If each team wins near equal matches, the runner-up will win ceil[ (N – 1)*(N – 2) / (2 * (N – 1)) ] = ceil[ (N – 2)/2 ]

If N is odd: The value is (N – 2 + 1)/2 = (N – 1)/2
If N is even: The value is (N – 2)/2. 

Matches difference when N is odd: (N – 1) – (N – 1)/2 = (N – 1)/2. So points difference = K * ((N – 1)/2).
Matches difference when N is even: (N – 1) – (N – 2)/2 = N/2. So points difference = K * (N / 2).

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Проверьте, является ли N нечетным или четным.
• Если N нечетно, требуемая разница равна K*((N-1)/2) .
• Если N равно требуемой разнице, это K*(N/2) .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(1)
Вспомогательное пространство: O(1)