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: Sí
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á ≤ 10Entrada: 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:
- Si N ≤ K: La persona que tenga el primer turno ganará el juego, es decir, A.
- 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.
- 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>
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