Editing 3007 - Tort 1 (section)

= Exemplu: =
<code>tort.in</code>
 6 6 3
 0 1 1 1 0 1
 1 0 0 0 0 1
 0 0 0 1 0 0
 0 1 0 1 0 1
 1 0 0 0 0 0
 1 1 1 0 0 1
<code>tort.out</code>
 10
 5

=== Explicație ===
Tortul este format dintr-un caroiaj cu <code>m = 6</code> linii şi <code>n = 6</code> coloane şi se pot tăia <code>k = 3</code> felii. Se pot obţine maximum <code>10</code> căpşuni. Cele <code>5</code> posibilităţi de a tăia cele trei felii sunt: <code>NNS</code>, <code>NSE</code>, <code>NSV</code>, <code>VEV</code> şi <code>NEV</code>.

<syntaxhighlight lang="python" line="1">
def count_strawberries(matrix):
    return sum(sum(row) for row in matrix)

def cut_slice(matrix, direction):
    if direction == 'N':
        return matrix[0], matrix[1:]
    elif direction == 'S':
        return matrix[-1], matrix[:-1]
    elif direction == 'E':
        return [row[-1] for row in matrix], [row[:-1] for row in matrix]
    elif direction == 'V':
        return [row[0] for row in matrix], [row[1:] for row in matrix]

def max_strawberries(matrix, k):
    from itertools import combinations_with_replacement
    
    m = len(matrix)
    n = len(matrix[0])
    directions = ['N', 'E', 'S', 'V']
    
    max_straws = 0
    for cuts in combinations_with_replacement(directions, k):
        temp_matrix = [row[:] for row in matrix]
        total_straws = 0
        for cut in cuts:
            slice_straws, temp_matrix = cut_slice(temp_matrix, cut)
            total_straws += sum(slice_straws)
        max_straws = max(max_straws, total_straws)
    
    return max_straws

# Exemplu de utilizare
matrix = [
    [0, 1, 0, 1, 0, 1],
    [1, 1, 0, 0, 1, 0],
    [0, 0, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0],
    [0, 1, 1, 0, 0, 1],
    [1, 0, 1, 0, 1, 0]
]
k = 3
print(max_strawberries(matrix, k))  # Afișează numărul maxim de căpșuni care pot fi obținute
</syntaxhighlight>