import numpy as np
from itertools import combinations

def dandc(arr: list[int], turn: str) -> str:
    if len(arr) == 1:
        return 'p1' if arr[0] == 0 else 'p2'

    other_player = 'p1' if turn == 'p2' else 'p2'
    mid = len(arr)//2
    left = dandc(arr[:mid], other_player)
    right = dandc(arr[mid:], other_player)

    if left == turn or right == turn:
        return turn
    return left

def get_all_options(n: int):
    """Returns all options for placing n zeros among n+1 ones"""
    size = 2 * n + 1
    ones_count = n + 1
    zeros_count = n
    base_array = np.ones(size, dtype=int)
    
    result = []
    for zero_positions in combinations(range(size), zeros_count):
        arr = base_array.copy()
        arr[list(zero_positions)] = 0
        result.append(arr.tolist())
    
    return result

def test() -> None:
    for n in range(1, 6):
        all_options = get_all_options(n)

        for option in all_options:
            print(f"Testing {option}...")
            if dandc(option, 'p1') == 'p1' and dandc(option, 'p2') == 'p1':
                print("FOUND!")
                print(option)
                return
    print("Not found...")


test()