21 Problema de fósforos

Dados 21 Matchsticks y 2 usuarios, A y B (computadora y usuario respectivamente). Los usuarios pueden escoger no más de cuatro cerillas a la vez. Pierde el que se ve obligado a recoger la última cerilla. 
Dada una array arr[] que contiene los movimientos de la computadora. La tarea es imprimir los movimientos del usuario para que el usuario gane el juego.
Ejemplos : 
 

Entrada: N = 4, arr=[ 3, 4, 2, 2] 
Salida: 2, 1, 3, 3 
Cuando la computadora elige 3 palos, el usuario elige 2 palos 
Cuando la computadora elige 4 palos, el usuario elige 1 palo 
Cuando la computadora elige 2 palos, el usuario elige 3 palos 
Cuando la computadora elige 2 palos, el usuario elige 3 palos 
Ahora solo queda 1 palo y la computadora se ve obligada a elegir ese palo 
Por lo tanto, el usuario gana el juego.
Entrada: N = 4 arr=[ 1, 1, 4, 3] 
Salida: 4, 4, 1, 2 
 

Acercarse: 
 

• La idea es pensar en 20 fósforos, ya que el usuario que elija el último perderá el juego.
• Divida 20 en cuatro partes, es decir, cada parte es de tamaño 5. Entonces, si la computadora elige x cerillas, entonces el usuario debe elegir (5-x) cerillas y debe proceder de la misma manera.
• De esta forma, se utilizarán 20 cerillas y la computadora recogerá la última cerilla.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the optimal strategy
void TwentyoneMatchstick(int arr[], int N)
{
 
    // Removing matchsticks in blocks of five
    for (int i = 0; i < N; i += 1) {
        cout << 5 - arr[i] << " ";
    }
    cout << endl;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 4, 2, 2 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    TwentyoneMatchstick(arr, N);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to return the optimal strategy
static void TwentyoneMatchstick(int arr[], int N)
{
 
    // Removing matchsticks in blocks of five
    for (int i = 0; i < N; i += 1)
    {
        System.out.print(5 - arr[i] + " ");
    }
    System.out.println();
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = {3, 4, 2, 2};
 
    int N = arr.length;
 
    TwentyoneMatchstick(arr, N);
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation of the approach
 
# Function to return the optimal strategy
def TwentyoneMatchstick(arr, N):
 
    # Removing matchsticks in blocks of five
    for i in range(N):
        print(5 - arr[i], end = " ")
 
# Driver code
arr = [3, 4, 2, 2 ]
 
N = len(arr)
 
TwentyoneMatchstick(arr, N)
 
# This code is contributed
# by Mohit Kumar

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the optimal strategy
static void TwentyoneMatchstick(int []arr, int N)
{
 
    // Removing matchsticks in blocks of five
    for (int i = 0; i < N; i += 1)
    {
        Console.Write(5 - arr[i] + " ");
    }
    Console.Write("\n");
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = {3, 4, 2, 2};
 
    int N = arr.Length;
 
    TwentyoneMatchstick(arr, N);
}
}
 
// This code is contributed by Princi Singh

// javascript implementation of the approach
   
// Function to return the optimal strategy
 function TwentyoneMatchstick(arr, N)
{
   
    // Removing matchsticks in blocks of five
    for (var i = 0; i < N; i += 1)
    {
        document.write(5 - arr[i] + " ");
    }
    document.write("<br>");
}
   
// Driver code
    var arr = [3, 4, 2, 2];
    var N = arr.length;
    TwentyoneMatchstick(arr, N);
 
// This code is contributed by bunnyram19.
  

2 1 3 3

Complejidad de tiempo: O(N)