Dado un número entero positivo N que representa el recuento de jugadores que juegan el juego. El juego se juega entre dos equipos, de modo que cada equipo consta de al menos un jugador, pero el recuento total de jugadores en el juego debe ser N. El juego dura exactamente 30 minutos , la tarea es verificar si todos los jugadores jugarán entre sí o no. Si el juego se puede jugar hasta T horas y se permite jugar el juego más de 1 vez. Si se encuentra que es cierto, imprima «Posible» . De lo contrario, imprima «No es posible» .
Ejemplos:
Entrada: N = 3, T = 1
Salida: Posible
explicación:
En la primera media hora, los jugadores { p 1 , p 2 } jugaron el partido contra { p 3 }.
En 2d medias horas, los jugadores { p 2 , P 3 } jugaron contra { p 1 }
ya que todos los jugadores jugaron entre sí dentro de T(=1) horas. Por lo tanto, la salida requerida es «Posible».Entrada: N = 4, T = 0,5
Salida: No es posible
Explicación:
En la primera media hora, los jugadores { p 1 , p 2 } jugaron el partido contra { p 3 , p 4 }.
Dado que el jugador p 1 no jugó el juego contra p 2 dentro de T(=0.5) horas. Por lo tanto, la salida requerida es «No posible».
Enfoque: El problema se puede resolver usando la técnica Greedy . Las siguientes son las observaciones:
- En cada juego, si uno de los dos equipos tiene un solo jugador, el juego debe jugarse N – 1 veces.
- En cada juego, si uno del equipo tiene N / 2 jugadores y el otro equipo tiene (N + 1) / 2 , entonces el juego debe jugarse (N + 1) / 2 veces.
Siga los pasos a continuación para resolver el problema:
- Si el tiempo total para jugar el juego N-1 veces es menor o igual a T , imprima «Posible» .
- Si el tiempo total para jugar el juego (N + 1) / 2 veces es menor o igual a T , entonces imprima «Posible» .
- De lo contrario, imprima «No es posible» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <iostream>
using namespace std;
// Function to find the N players
// the game against each other or not
string calculate(int N, int T)
{
// Base Case
if (N <= 1 || T <= 0) {
// Return -1 if not valid
return "-1";
}
// Converting hours into minutes
int minutes = T * 60;
// Calculating maximum games that
// can be played.
int max_match = N - 1;
// Time required for conducting
// maximum games
int max_time = max_match * 30;
// Checking if it is possible
// to conduct maximum games
if (max_time <= minutes) {
// Return possible
return "Possible";
}
// Calculating minimum games
int min_match = N / 2;
min_match = N - min_match;
// Time required for conducting
// minimum games
int min_time = min_match * 30;
// Checking if it is possible
// to conduct minimum games
if (min_time <= minutes) {
// Return possible
return "Possible";
}
// Return not possible if time
// is less than required time
return "Not Possible";
}
// Driver Code
// Total count of players
int main()
{
int N = 6, T = 2;
// function call
cout << calculate(N, T);
return 0;
}
// This code is contributed by Parth Manchanda
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to find the N players
// the game against each other or not
static String calculate(int N, int T)
{
// Base Case
if (N <= 1 || T <= 0) {
// Return -1 if not valid
return "-1";
}
// Converting hours into minutes
int minutes = T * 60;
// Calculating maximum games that
// can be played.
int max_match = N - 1;
// Time required for conducting
// maximum games
int max_time = max_match * 30;
// Checking if it is possible
// to conduct maximum games
if (max_time <= minutes) {
// Return possible
return "Possible";
}
// Calculating minimum games
int min_match = N / 2;
min_match = N - min_match;
// Time required for conducting
// minimum games
int min_time = min_match * 30;
// Checking if it is possible
// to conduct minimum games
if (min_time <= minutes) {
// Return possible
return "Possible";
}
// Return not possible if time
// is less than required time
return "Not Possible";
}
// Driver code
public static void main(String[] args)
{
int N = 6, T = 2;
// function call
System.out.println(calculate(N, T));
}
}
// This code is contributed by sanjoy_62.
Python3
# Python program for the above problem # Function to find the N players # the game against each other or not def calculate(N, T): # Base Case if N <= 1 or T <= 0: # Return -1 if not valid return -1 # Converting hours into minutes minutes = T * 60 # Calculating maximum games that # can be played. max_match = N - 1 # Time required for conducting # maximum games max_time = max_match * 30 # Checking if it is possible # to conduct maximum games if max_time <= minutes: # Return possible return "Possible" # Calculating minimum games min_match = N//2 min_match = N - min_match # Time required for conducting # minimum games min_time = min_match * 30 # Checking if it is possible # to conduct minimum games if min_time <= minutes: # Return possible return "Possible" # Return not possible if time # is less than required time return "Not Possible" # Driver Code if __name__ == "__main__": # Total count of players N = 6 # Given hours T = 2 # Function call ans = calculate(N, T) # Print ans print(ans)
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the N players
// the game against each other or not
static string calculate(int N, int T)
{
// Base Case
if (N <= 1 || T <= 0) {
// Return -1 if not valid
return "-1";
}
// Converting hours into minutes
int minutes = T * 60;
// Calculating maximum games that
// can be played.
int max_match = N - 1;
// Time required for conducting
// maximum games
int max_time = max_match * 30;
// Checking if it is possible
// to conduct maximum games
if (max_time <= minutes) {
// Return possible
return "Possible";
}
// Calculating minimum games
int min_match = N / 2;
min_match = N - min_match;
// Time required for conducting
// minimum games
int min_time = min_match * 30;
// Checking if it is possible
// to conduct minimum games
if (min_time <= minutes) {
// Return possible
return "Possible";
}
// Return not possible if time
// is less than required time
return "Not Possible";
}
// Driver Code
public static void Main(String[] args)
{
int N = 6, T = 2;
// function call
Console.WriteLine(calculate(N, T));
}
}
// This code is contributed by splevel62.
Javascript
<script>
// JavaScript Program for the above approach
// Function to find the N players
// the game against each other or not
function calculate(N, T)
{
// Base Case
if (N <= 1 || T <= 0)
{
// Return -1 if not valid
return -1;
}
// Converting hours into minutes
let minutes = T * 60;
// Calculating maximum games that
// can be played.
let max_match = N - 1
// Time required for conducting
// maximum games
max_time = max_match * 30
// Checking if it is possible
// to conduct maximum games
if (max_time <= minutes)
{
// Return possible
return "Possible";
}
// Calculating minimum games
min_match = Math.floor(N / 2);
min_match = N - min_match
// Time required for conducting
// minimum games
min_time = min_match * 30;
// Checking if it is possible
// to conduct minimum games
if (min_time <= minutes)
{
// Return possible
return "Possible";
// Return not possible if time
// is less than required time
return "Not Possible";
}
}
// Driver Code
// Total count of players
let N = 6
// Given hours
let T = 2
// Function call
let ans = calculate(N, T)
// Print ans
document.write(ans);
// This code is contributed by Potta Lokesh
</script>
Possible
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rakshitarora y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA