Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
940 B
4
Indexable
Never
def min_moves(n):
    """
    Returns the minimum number of moves required to reduce the enemy army to 1 soldier.
    
    :param n: The number of enemy soldiers.
    :return: The minimum number of moves.
    """
    memo = {1: 0}  # Base case: 0 moves required for 1 soldier

    def recursive_min_moves(n):
        if n in memo:
            return memo[n]
        
        # Try all three moves and choose the one with the minimum number of moves
        move1 = recursive_min_moves(n - 1) + 1
        move2 = recursive_min_moves(n // 2) + 1 if n % 2 == 0 else float('inf')
        move3 = recursive_min_moves(n // 3) + 1 if n % 3 == 0 else float('inf')
        
        # Store the result in the memo dictionary
        memo[n] = min(move1, move2, move3)
        return memo[n]
    
    return recursive_min_moves(n)

# Example usage:
n = int(input("Enter the number of enemy soldiers: "))
print("Minimum number of moves:", min_moves(n))
Leave a Comment