Encuentra al jugador que gana el juego eliminando la última de las N cartas dadas

Dados dos números enteros N y K , donde N representa el número total de cartas presentes cuando comienza el juego y K denota el número máximo de cartas que se pueden quitar en un solo turno. Dos jugadores A y B se turnan para quitar como máximo K cartas, una por una, comenzando por el jugador A. El jugador que quita la última carta es el ganador. La tarea es verificar si A puede ganar el juego o no. Si es cierto, escriba ‘A’ como respuesta. De lo contrario, imprime ‘B’ .

Ejemplos:

Entrada: N = 14, K = 10
Salida:
Explicación: 
Turno 1: A quita 3 cartas en su primer turno. 
Turno 2: B elimina cualquier número de cartas del rango [1 – 10] 
Finalmente, A puede eliminar todas las cartas restantes y gana el juego, ya que el número de cartas restantes después del turno 2 será ≤ 10

Entrada: N= 11, K=10
Salida: No

Enfoque: La idea aquí es observar que siempre que el valor de N % (K + 1) = 0 , entonces A nunca podrá ganar el juego. De lo contrario , A siempre gana el juego. 
Prueba:

  1. Si N ≤ K: La persona que tenga el primer turno ganará el juego, es decir, A.
  2. Si N = K + 1: A puede eliminar cualquier número de cartas en el rango [1, K] . Entonces, el número total de cartas que quedan después del primer turno también están en el rango [1, K] . Ahora B obtiene el turno y el número de cartas que quedan están en el rango [1, K] . Entonces, B ganará el juego.
  3. Si K + 2 ≤ N ≤ 2K + 1: A quita N – (K + 1) cartas en su primer turno. B puede eliminar cualquier número de cartas en el rango [1, K] en el próximo turno. Por lo tanto, el número total de cartas que quedan ahora están en el rango [1, K] . Ahora, dado que las cartas restantes están en el rango [1, K] , entonces A puede quitar todas las cartas y ganar el juego.

Por tanto la idea es comprobar si N % (K + 1) es igual a 0 o no. Si se determina que es cierto, imprima B como el ganador. De lo contrario, imprima A como ganador.
A continuación se muestra la implementación del enfoque anterior:

C++

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check which
// player can win the game
void checkWinner(int N, int K)
{
    if (N % (K + 1)) {
        cout << "A";
    }
    else {
        cout << "B";
    }
}
 
// Driver code
int main()
{
 
    int N = 50;
    int K = 10;
    checkWinner(N, K);
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to check which
// player can win the game
static void checkWinner(int N, int K)
{
    if (N % (K + 1) > 0)
    {
        System.out.print("A");
    }
    else
    {
        System.out.print("B");
    }
}
 
// Driver code
public static void main(String[] args)
{
    int N = 50;
    int K = 10;
     
    checkWinner(N, K);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to implement
# the above approach
 
# Function to check which
# player can win the game
def checkWinner(N, K):
 
    if(N % (K + 1)):
        print("A")
    else:
        print("B")
 
# Driver Code
N = 50
K = 10
 
# Function call
checkWinner(N, K)
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to check which
// player can win the game
static void checkWinner(int N, int K)
{
    if (N % (K + 1) > 0)
    {
        Console.Write("A");
    }
    else
    {
        Console.Write("B");
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 50;
    int K = 10;
     
    checkWinner(N, K);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
    // Javascript Program to implement
// the above approach
 
// Function to check which
// player can win the game
function checkWinner(N, K)
{
    if (N % (K + 1)) {
        document.write("A");
    }
    else {
        document.write("B");
    }
}
 
// Driver code
 
    let N = 50;
    let K = 10;
    checkWinner(N, K);
 
// This code is contributed by Saurabh Jaiswal
</script>
Producción: 

A

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

Publicación traducida automáticamente

Artículo escrito por shashanktrivedi02 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *