Diferencia máxima de puntos entre el ganador y el subcampeón del Torneo

Dados los números enteros N y K , que denotan el número de equipos que participan en un torneo de fútbol en el que cada equipo juega solo un partido entre sí, la tarea es encontrar la diferencia máxima de puntos entre el ganador y el subcampeón (segundo lugar). del torneo donde el ganador de un partido obtiene K puntos.

Ejemplos:

Entrada: N = 2, K = 4
Salida: 4 
Explicación: Si hay 2 equipos A y B, A ganará o perderá.
Si A gana el partido, obtiene 4 puntos y el equipo B obtiene 0.
Por lo tanto, la máxima diferencia posible de puntos entre el equipo ganador y el segundo clasificado es 4.

Entrada: N = 3, K = 4
Salida: 4

Entrada: N = 9, K = 5
Salida: 20

Planteamiento: el problema se puede resolver con base en la siguiente observación matemática:

La diferencia será máxima cuando el ganador gane todos los partidos que juegue y todos los demás equipos ganen partidos casi iguales cada uno. Como cada vez se juega contra otros solo una vez, el número total de partidos es N * (N – 1)/2.

Si el ganador gana todos los partidos (es decir, (N-1) partidos que juega), el número restante de partidos es:
(N * (N – 1))/2 – (N – 1) = (N – 1) * (N-2) / 2 .
Si cada equipo gana partidos casi igualados, el subcampeón ganará ceil[ (N – 1)*(N – 2) / (2 * (N – 1)) ] = ceil[ (N – 2)/2 ]

Si N es impar: El valor es (N – 2 + 1)/2 = (N – 1)/2
Si N es par: El valor es (N – 2)/2 . 

Coincide con la diferencia cuando N es impar: (N – 1) – (N – 1)/2 = (N – 1)/2. Entonces diferencia de puntos = K * ((N – 1)/2) .
Iguala la diferencia cuando N es par: (N – 1) – (N – 2)/2 = N/2. Entonces diferencia de puntos = K * (N / 2) .

Siga los pasos mencionados a continuación para implementar la idea:

• Comprueba si N es par o impar.
• Si N es impar, la diferencia requerida es K*((N-1)/2) .
• Si N es par, la diferencia requerida es K*(N/2) .

A continuación se muestra la implementación del enfoque anterior.

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate point difference
int pointDiff(int N, int K)
{
 
  // If N is odd
  if (N % 3 != 0)
    return ((N - 1) / 2) * K;
 
  // If N is even
  return (N / 2) * K;
}
 
// Driver code
int main()
{
  int N = 9, K = 5;
 
  // Function call
  cout << pointDiff(N, K);
 
  return 0;
}
 
// This code is contributed by rakeshsahni

// Java code to implement the approach
 
import java.util.*;
 
class GFG {
 
    // Function to calculate point difference
    public static int pointDiff(int N, int K)
    {
        // If N is odd
        if (N % 3 != 0)
            return ((N - 1) / 2) * K;
 
        // If N is even
        return (N / 2) * K;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 9, K = 5;
 
        // Function call
        System.out.println(pointDiff(N, K));
    }
}

# Python code to implement the approach
 
# Function to calculate point difference
def pointDiff(N, K):
   
    # If N is odd
    if N % 3 != 0:
        return ((N - 1) // 2) * K
       
    # If N is even
    return (N // 2) * K
 
# Driver code
if __name__ == "__main__":
    N = 9
    K = 5
    # Function call
    print(pointDiff(N, K))
 
# This code is contributed by Rohit Pradhan

// C# code to implement the approach
using System;
using System.Linq;
 
public class GFG
{
  // Function to calculate point difference
  public static int pointDiff(int N, int K)
  {
    // If N is odd
    if (N % 3 != 0)
      return ((N - 1) / 2) * K;
 
    // If N is even
    return (N / 2) * K;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int N = 9, K = 5;
 
    // Function call
    Console.WriteLine(pointDiff(N, K));
  }
}
 
// This code is contributed by code_hunt.

<script>
 
// JavaScript code to implement the approach
 
 
// Function to calculate point difference
function pointDiff(N, K)
{
 
  // If N is odd
  if (N % 3 != 0)
    return Math.floor((N - 1) / 2) * K;
 
  // If N is even
  return Math.floor(N / 2) * K;
}
 
// Driver code
 
let N = 9, K = 5;
 
// Function call
document.write(pointDiff(N, K),"</br>");
 
 
// This code is contributed by shinjanpatra
 
</script>

20

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)