Editing 3007 - Tort 1

De ziua lui, Gigel a primit un tort de formă dreptunghiulară, ornat cu un caroiaj ce împarte tortul în <code>m x n</code> pătrate, în fiecare pătrat aflându-se câte o cireașă sau o căpșună. Caroiajul cu fructe este reprezentat printr-o matrice cu <code>0</code> şi <code>1</code>, <code>0</code> însemnând cireaşă şi <code>1</code> căpşună. Sărbătoritul are dreptul să taie <code>k</code> felii de tort. O felie se poate obține prin tăierea după liniile caroiajului, dintr-un capăt în celălalt, având lățimea egală cu <code>1</code>, de pe oricare latură a tortului, codificate cu <code>N</code>, <code>E</code>, <code>S</code>, <code>V</code>. Gigel fiind mare amator de căpşuni vrea să taie cele <code>k</code> felii astfel încât numărul căpşunilor din aceste felii să fie cât mai mare. Spre exemplu, dacă tortul iniţial este reprezentat ca o matrice având <code>6 x 6</code> linii şi coloane, după <code>3</code> tăieturi <code>N</code>, <code>E</code>, <code>V</code> bucata rămasă şi feliile obţinute vor fi conform figurii alăturate.

= Cerința =
Să se scrie un program care să determine numărul de posibilităţi de tăiere a <code>k</code> felii de tort, pentru a obţine un număr maxim de căpşuni. Două variante în care diferă doar ordinea de tăiere, dar rămâne aceeaşi bucată de tort, nu sunt considerate distincte. De exemplu, dacă numărul maxim de căpşuni se poate obţine prin una din variantele : <code>VSNNV</code> sau <code>VVNSN</code>, acestea nu sunt considerate distincte.

= Date de intrare =
Pe prima linie a fişierului de intrare <code>tort.in</code> sunt scrise dimensiunile tortului, <code>m</code> şi <code>n</code> şi numărul <code>k</code> al feliilor de tort tăiate de Gigel, separate prin câte un spaţiu. Pe următoarele <code>m</code> linii e descris caroiajul cu fructe printr-o matrice cu valori de <code>0</code> şi <code>1</code>.

= Date de ieșire =
Prima linie a fişierului <code>tort.out</code> va conţine numărul maxim de căpşuni care poate fi obţinut din cele <code>k</code> felii de tort. Pe linia a doua se va găsi numărul de posibilităţi distincte de a obţine numărul maxim de căpşuni.

= Restricții și precizări =

* <code>2 ≤ m, n ≤ 500</code>
* <code>1 ≤ k < min(m, n)</code>

= 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>