Dado un número entero N que denota el número de cajas en un corral, y dos jugadores P1 y P2 jugando un juego de distribución de N bolígrafos entre ellos según las siguientes reglas:
- P1 hace el primer movimiento tomando 2 bolígrafos X. (Inicialmente, X = 0)
- P2 toma 3 bolígrafos X.
- El valor de X aumenta en 1 después de cada movimiento.
- P1 y P2 hacen movimiento alternativamente.
- Si el jugador actual tiene que tomar más bolígrafos que el número de bolígrafos que quedan en la caja, entonces se retira.
- El juego terminará cuando ambos jugadores abandonen o cuando la caja se quede vacía.
La tarea de imprimir los siguientes detalles una vez que termine el juego:
- El número de bolígrafos que quedan en la caja.
- El número de bolígrafos recolectados por P1 .
- El número de bolígrafos recogidos por P2 .
Ejemplos:
Entrada: N = 22
Salida:
Número de bolígrafos que quedan en la caja: 14
Número de bolígrafos recogidos por P1: 5
Número de bolígrafos recogidos por P2: 3
Explicación:
- Movimiento 1: X = 0, P1 toma 1 bolígrafo de la caja. Por lo tanto, N = 22 – 1 = 21.
- Movimiento 2: X = 1, P2 toma 3 bolígrafos de la caja. Por lo tanto, N = 21 – 3 = 18.
- Movimiento 3: X = 2, P1 toma 4 bolígrafos de la caja. Por lo tanto, N = 18 – 4 = 14.
- Movimiento 4: X = 3, P2 sale como 27 > 14.
- Movimiento 5: X = 4, P1 sale como 16 > 14.
- ¡Juego terminado! Ambos jugadores han renunciado.
Entrada: N = 1
Salida:
Número de bolígrafos que quedan en la caja: 0
Número de bolígrafos recogidos por P1: 1
Número de bolígrafos recogidos por P2: 0
Enfoque : La idea es usar Recursión . Siga los pasos para resolver el problema:
1. Defina una función recursiva:
Game_Move(N, P1, P2, X, Move, QuitP1, QuitP2)
donde,
N : Número total de bolígrafos
P1 : Puntuación de P1
P2 : Puntuación de P2
X : Inicializado a cero
Move = 0 : Turno de P1
Move = 1 : P2’s gire
QuitP1 : P1 ha
salido QuitP2 : P2 ha salido
2. Finalmente, imprime los valores finales después de que el juego haya terminado.
A continuación se muestra la implementación del enfoque mencionado anteriormente:
C++
// C++ implementation of the // above approach #include <bits/stdc++.h> using namespace std; // N = Total number of Pens // P1 : Score of P1 // P2 : Score of P2 // X : Initialized to zero // Move = 0 : P1's turn // Move = 1 : P2's turn // QuitP1 : Has P1 quit // QuitP2 : Has P2 quit // Recursive function to play Game void solve(int& N, int& P1, int& P2, int& X, bool Move, bool QuitP1, bool QuitP2) { if (N == 0 or (QuitP1 and QuitP2)) { // Box is empty, Game Over! or // Both have quit, Game Over! cout << "Number of pens remaining" << " in the box: " << N << endl; cout << "Number of pens collected" << " by P1: " << P1 << endl; cout << "Number of pens collected" << " by P2: " << P2 << endl; return; } if (Move == 0 and QuitP1 == false) { // P1 moves int req_P1 = pow(2, X); if (req_P1 <= N) { P1 += req_P1; N -= req_P1; } else { QuitP1 = true; } } else if (Move == 1 and QuitP2 == false) { // P2 moves int req_P2 = pow(3, X); if (req_P2 <= N) { P2 += req_P2; N -= req_P2; } else { QuitP2 = true; } } // Increment X X++; // Switch moves between P1 and P2 Move = ((Move == 1) ? 0 : 1); solve(N, P1, P2, X, Move, QuitP1, QuitP2); } // Function to find the number of // pens remaining in the box and // calculate score for each player void PenGame(int N) { // Score of P1 int P1 = 0; // Score of P2 int P2 = 0; // Initialized to zero int X = 0; // Move = 0, P1's turn // Move = 1, P2's turn bool Move = 0; // Has P1 quit bool QuitP1 = 0; // Has P2 quit bool QuitP2 = 0; // Recursively continue the game solve(N, P1, P2, X, Move, QuitP1, QuitP2); } // Driver Code int main() { int N = 22; PenGame(N); return 0; }
Java
// Java implementation of the // above approach import java.util.*; import java.lang.*; public class GFG { // N = Total number of Pens // P1 : Score of P1 // P2 : Score of P2 // X : Initialized to zero // Move = 0 : P1's turn // Move = 1 : P2's turn // QuitP1 : Has P1 quit // QuitP2 : Has P2 quit // Recursive function to play Game static void solve(int N, int P1, int P2, int X, int Move, boolean QuitP1, boolean QuitP2) { if (N == 0 || (QuitP1 && QuitP2)) { // Box is empty, Game Over! or // Both have quit, Game Over! System.out.println("Number of pens remaining" + " in the box: " + N); System.out.println("Number of pens collected" + " by P1: " + P1); System.out.println("Number of pens collected" + " by P2: " + P2); return; } if (Move == 0 && QuitP1 == false) { // P1 moves int req_P1 = (int)(Math.pow(2, X)); if (req_P1 <= N) { P1 += req_P1; N -= req_P1; } else { QuitP1 = true; } } else if (Move == 1 && QuitP2 == false) { // P2 moves int req_P2 = (int)(Math.pow(3, X)); if (req_P2 <= N) { P2 += req_P2; N -= req_P2; } else { QuitP2 = true; } } // Increment X X++; // Switch moves between P1 and P2 Move = ((Move == 1) ? 0 : 1); solve(N, P1, P2, X, Move, QuitP1, QuitP2); } // Function to find the number of // pens remaining in the box and // calculate score for each player static void PenGame(int N) { // Score of P1 int P1 = 0; // Score of P2 int P2 = 0; // Initialized to zero int X = 0; // Move = 0, P1's turn // Move = 1, P2's turn int Move = 0; // Has P1 quit boolean QuitP1 = false; // Has P2 quit boolean QuitP2 = false; // Recursively continue the game solve(N, P1, P2, X, Move, QuitP1, QuitP2); } // Driver Code public static void main (String[] args) { int N = 22; PenGame(N); } } // This code is contributed by jana_sayantan.
Python3
# Python3 implementation of the # above approach # N = Total number of Pens # P1 : Score of P1 # P2 : Score of P2 # X : Initialized to zero # Move = 0 : P1's turn # Move = 1 : P2's turn # QuitP1 : Has P1 quit # QuitP2 : Has P2 quit # Recursive function to play Game def solve(N, P1, P2, X, Move, QuitP1, QuitP2): if (N == 0 or (QuitP1 and QuitP2)): # Box is empty, Game Over! or # Both have quit, Game Over! print("Number of pens remaining in the box: ", N) print("Number of pens collected by P1: ", P1) print("Number of pens collected by P2: ", P2) return if (Move == 0 and QuitP1 == False): # P1 moves req_P1 = int(pow(2, X)) if (req_P1 <= N): P1 += req_P1 N -= req_P1 else: QuitP1 = True elif (Move == 1 and QuitP2 == False): # P2 moves req_P2 = int(pow(3, X)) if (req_P2 <= N): P2 += req_P2 N -= req_P2 else: QuitP2 = True # Increment X X += 1 # Switch moves between P1 and P2 if(Move == 1): Move = 0 else: Move = 1 solve(N, P1, P2, X, Move, QuitP1, QuitP2) # Function to find the number of # pens remaining in the box and # calculate score for each player def PenGame(N): # Score of P1 P1 = 0 # Score of P2 P2 = 0 # Initialized to zero X = 0 # Move = 0, P1's turn # Move = 1, P2's turn Move = False # Has P1 quit QuitP1 = False # Has P2 quit QuitP2 = False # Recursively continue the game solve(N, P1, P2, X, Move, QuitP1, QuitP2) # Driver Code N = 22 PenGame(N) # This code is contributed by Dharanendra L V.
C#
// C# implementation of the // above approach using System; class GFG { // N = Total number of Pens // P1 : Score of P1 // P2 : Score of P2 // X : Initialized to zero // Move = 0 : P1's turn // Move = 1 : P2's turn // QuitP1 : Has P1 quit // QuitP2 : Has P2 quit // Recursive function to play Game static void solve(int N, int P1, int P2, int X, int Move, bool QuitP1, bool QuitP2) { if (N == 0 || (QuitP1 && QuitP2)) { // Box is empty, Game Over! or // Both have quit, Game Over! Console.WriteLine("Number of pens remaining" + " in the box: " + N); Console.WriteLine("Number of pens collected" + " by P1: " + P1); Console.WriteLine("Number of pens collected" + " by P2: " + P2); return; } if (Move == 0 && QuitP1 == false) { // P1 moves int req_P1 = (int)(Math.Pow(2, X)); if (req_P1 <= N) { P1 += req_P1; N -= req_P1; } else { QuitP1 = true; } } else if (Move == 1 && QuitP2 == false) { // P2 moves int req_P2 = (int)(Math.Pow(3, X)); if (req_P2 <= N) { P2 += req_P2; N -= req_P2; } else { QuitP2 = true; } } // Increment X X++; // Switch moves between P1 and P2 Move = ((Move == 1) ? 0 : 1); solve(N, P1, P2, X, Move, QuitP1, QuitP2); } // Function to find the number of // pens remaining in the box and // calculate score for each player static void PenGame(int N) { // Score of P1 int P1 = 0; // Score of P2 int P2 = 0; // Initialized to zero int X = 0; // Move = 0, P1's turn // Move = 1, P2's turn int Move = 0; // Has P1 quit bool QuitP1 = false; // Has P2 quit bool QuitP2 = false; // Recursively continue the game solve(N, P1, P2, X, Move, QuitP1, QuitP2); } // Driver Code public static void Main() { int N = 22; PenGame(N); } } // This code is contributed by chitranayal.
Javascript
<script> // javascript program of the above approach // N = Total number of Pens // P1 : Score of P1 // P2 : Score of P2 // X : Initialized to zero // Move = 0 : P1's turn // Move = 1 : P2's turn // QuitP1 : Has P1 quit // QuitP2 : Has P2 quit // Recursive function to play Game function solve(N, P1, P2, X, Move, QuitP1, QuitP2) { if (N == 0 || (QuitP1 && QuitP2)) { // Box is empty, Game Over! or // Both have quit, Game Over! document.write("Number of pens remaining" + " in the box: " + N + "<br/>"); document.write("Number of pens collected" + " by P1: " + P1+ "<br/>"); document.write("Number of pens collected" + " by P2: " + P2+ "<br/>"); return; } if (Move == 0 && QuitP1 == false) { // P1 moves let req_P1 = (Math.pow(2, X)); if (req_P1 <= N) { P1 += req_P1; N -= req_P1; } else { QuitP1 = true; } } else if (Move == 1 && QuitP2 == false) { // P2 moves let req_P2 = (Math.pow(3, X)); if (req_P2 <= N) { P2 += req_P2; N -= req_P2; } else { QuitP2 = true; } } // Increment X X++; // Switch moves between P1 and P2 Move = ((Move == 1) ? 0 : 1); solve(N, P1, P2, X, Move, QuitP1, QuitP2); } // Function to find the number of // pens remaining in the box and // calculate score for each player function PenGame(N) { // Score of P1 let P1 = 0; // Score of P2 let P2 = 0; // Initialized to zero let X = 0; // Move = 0, P1's turn // Move = 1, P2's turn let Move = 0; // Has P1 quit let QuitP1 = false; // Has P2 quit let QuitP2 = false; // Recursively continue the game solve(N, P1, P2, X, Move, QuitP1, QuitP2); } // Driver Code let N = 22; PenGame(N); </script>
Number of pens remaining in the box: 14 Number of pens collected by P1: 5 Number of pens collected by P2: 3
Complejidad de tiempo: O(Log(N))
Espacio auxiliar: O(1)