def find_max(arr, low, high):
    # Cas base: Si la llista té un sol element
    if low == high:
        return arr[low]
    
    # Divideix la llista en dues meitats
    mid = (low + high) // 2
    
    # Troba el màxim en cada meitat
    max1 = find_max(arr, low, mid)
    max2 = find_max(arr, mid + 1, high)
    
    # Retorna el màxim dels dos
    return max(max1, max2)

# Exemple d'ús
arr = [1, 5, 3, 9, 2, 8, 4]
resultat = find_max(arr, 0, len(arr) - 1)
print(f"L'element màxim és: {resultat}")

class Objecte:
    def __init__(self, pes, valor):
        self.pes = pes
        self.valor = valor
        self.ratio = valor / pes

def motxilla_fraccionaria(objectes, capacitat):
    # Ordena els objectes per valor per unitat de pes en ordre descendent
    objectes.sort(key=lambda x: x.ratio, reverse=True)
    
    valor_total = 0
    for obj in objectes:
        if capacitat >= obj.pes:
            capacitat -= obj.pes
            valor_total += obj.valor
        else:
            valor_total += obj.valor * (capacitat / obj.pes)
            break
    
    return valor_total

# Exemple d'ús
objectes = [Objecte(10, 60), Objecte(20, 100), Objecte(30, 120)]
capacitat = 50
resultat = motxilla_fraccionaria(objectes, capacitat)
print(f"El valor màxim que es pot obtenir és: {resultat}")

def cami_minim(mat):
    if not mat or not mat[0]:
        return 0
    
    n, m = len(mat), len(mat[0])
    dp = [[0] * m for _ in range(n)]
    
    dp[0][0] = mat[0][0]
    
    # Inicialitza la primera fila
    for j in range(1, m):
        dp[0][j] = dp[0][j-1] + mat[0][j]
    
    # Inicialitza la primera columna
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] + mat[i][0]
    
    # Omple la resta de la matriu dp
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = mat[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    return dp[n-1][m-1]

# Exemple d'ús
matriu = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
resultat = cami_minim(matriu)
print(f"El camí mínim té un cost de: {resultat}")

def es_segura(board, row, col, n):
    # Comprova la fila a l'esquerra
    for i in range(col):
        if board[row][i] == 1:
            return False
    
    # Comprova la diagonal superior esquerra
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    
    # Comprova la diagonal inferior esquerra
    for i, j in zip(range(row, n, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    
    return True

def soluciona_n_reines(board, col, n):
    if col >= n:
        return True
    
    for i in range(n):
        if es_segura(board, i, col, n):
            board[i][col] = 1
            if soluciona_n_reines(board, col + 1, n):
                return True
            board[i][col] = 0
    
    return False

def n_reines(n):
    board = [[0] * n for _ in range(n)]
    if not soluciona_n_reines(board, 0, n):
        return "No hi ha solució"
    return board

# Exemple d'ús
n = 4
resultat = n_reines(n)
for fila in resultat:
    print(fila)