There are N teams numbered from 1 to N in a league tournament. Given an integer K, the task is to find the maximum possible points a team finishing at Kth position can score.
It is given that, a team will get 2 points on winning while 0 points on losing.
Note: A league tournament is also known as round-robin tournament where each team plays with every other team exactly once.
Examples:
Input: N = 2, K = 2
Output: 0
Explanation: Total number of matches = 2C2 = 1
Maximum possible win for team at 2nd position = 0
The final score for team having rank 2 = 2 * 0 = 0 PointsInput: N = 5, K =3
Output: 6
Explanation: Total number of matches = nC2 = 10
Maximum possible win for team at 3rd position = 3
The final score for team 3 = 2 * = 6
Approach: The solution of the problem is based on the following observation:
- Suppose team i finishes at ith i.e team1 finishes at 1st position, team 2 finishes at 2nd position and so on. Also the score of team i will be greater than or equal to j for all i <= j.
- For K = N, If teamN (the team which finishes at last position) wins X rounds, then all other teams must wins at least X rounds. It is also known that total number of rounds in tournament is NC2 . Now calculate the maximum value of X:
- As X Win will be less than or equal to total number of wins of all teams
X <= NC2 /N = (N-1)/2
So the maximum value of X is (N- 1) / 2 . Here X denotes the number of wins by team N against first (N -1) teams.- Now team K will win at most (N – K) rounds against last (N – K) teams and (K – 1) / 2 rounds against first (K -1 ) teams. The total maximum win by team k will be summation of win against first (K -1) and last (N – K) teams. i.e
N – K + (K-1)/2 = (2*N – K – 1)/2 matches.
Follow the steps mentioned below to implement the above observation:
- For the given value of N and K, the number of maximum possible win for the team finishing at Kth position is (2*N – K -1)/2.
- Now calculate the final score by multiplying the calculated max possible win by 2.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate// maximum points scored by the// team finishing at kth positionint maxScore(int N, int K){ // Calculate Maximum wins // using formula int maxWins = (2 * N - K - 1) / 2; // Multiply max wins by 2 // to get total points int totalPoints = maxWins * 2; return totalPoints;}// Driver codeint main(){ int N = 5; int k = 3; cout << maxScore(N, k); return 0;} |
Java
// JAVA program for the above approachimport java.util.*;class GFG{ // Function to calculate // maximum points scored by the // team finishing at kth position public static int maxScore(int N, int K) { // Calculate Maximum wins // using formula int maxWins = (2 * N - K - 1) / 2; // Multiply max wins by 2 // to get total points int totalPoints = maxWins * 2; return totalPoints; } // Driver code public static void main(String[] args) { int N = 5; int k = 3; System.out.print(maxScore(N, k)); }}// This code is contributed by Taranpreet |
Python3
# Python code for the above approach # Function to calculate# maximum points scored by the# team finishing at kth positiondef maxScore(N, K): # Calculate Maximum wins # using formula maxWins = (2 * N - K - 1) / 2; # Multiply max wins by 2 # to get total points totalPoints = maxWins * 2; return int(totalPoints)# Driver codeN = 5;k = 3;print(maxScore(N, k));# This code is contributed by Saurabh jaiswal |
C#
// C# program for the above approachusing System;class GFG{ // Function to calculate // maximum points scored by the // team finishing at kth position static int maxScore(int N, int K) { // Calculate Maximum wins // using formula int maxWins = (2 * N - K - 1) / 2; // Multiply max wins by 2 // to get total points int totalPoints = maxWins * 2; return totalPoints; } // Driver code public static void Main() { int N = 5; int k = 3; Console.Write(maxScore(N, k)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to calculate // maximum points scored by the // team finishing at kth position function maxScore(N, K) { // Calculate Maximum wins // using formula let maxWins = (2 * N - K - 1) / 2; // Multiply max wins by 2 // to get total points let totalPoints = maxWins * 2; return totalPoints; } // Driver code let N = 5; let k = 3; document.write(maxScore(N, k)); // This code is contributed by Potta Lokesh </script> |
6
Time Complexity: O(1)
Auxiliary Space: O(1)
