Editing 4171 - Loop Over (section)

= Exemplul 4: =
<code>loopover.in</code>
 2 8
 10
 R 6
 L 8
 R 4
 U 3
 L 3
 L 1
 R 3
 U 5
 U 6
 U 3
<code>loopover.out</code>
 4284

=== Explicație ===
Sunt necesare <code>4284</code> de aplicări ale secvenței pentru a reveni în starea inițială.

<syntaxhighlight lang="python" line="1">
MOD = 1000000007

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def min_operations_to_initial(n, grid, is_row_operations):
    if is_row_operations:
        operations_needed = 0
        for row in grid:
            for j in range(n):
                if row[j] != (row[0] + j) % n:
                    shift_amount = (j - row.index(1)) % n
                    operations_needed = gcd(operations_needed, shift_amount)
        return operations_needed
    else:
        operations_needed = 0
        for j in range(n):
            col = [grid[i][j] for i in range(n)]
            for i in range(n):
                if col[i] != (col[0] + i * n) % (n * n):
                    shift_amount = (i - col.index(1)) % n
                    operations_needed = gcd(operations_needed, shift_amount)
        return operations_needed

def min_apply_sequence(n, sequence):
    length_sequence = len(sequence)
    current_pos = list(range(n * n))
    for op in sequence:
        direction, idx = op.split()
        idx = int(idx) - 1
        if direction == 'L':
            row = current_pos[idx * n:(idx + 1) * n]
            current_pos[idx * n:(idx + 1) * n] = row[1:] + row[:1]
        elif direction == 'R':
            row = current_pos[idx * n:(idx + 1) * n]
            current_pos[idx * n:(idx + 1) * n] = row[-1:] + row[:-1]
        elif direction == 'U':
            col = current_pos[idx::n]
            current_pos[idx::n] = col[1:] + col[:1]
        elif direction == 'D':
            col = current_pos[idx::n]
            current_pos[idx::n] = col[-1:] + col[:-1]
    target_pos = list(range(n * n))
    if current_pos == target_pos:
        return 1
    cycle_length = 1
    while True:
        current_pos = list(range(n * n))
        for _ in range(cycle_length):
            for op in sequence:
                direction, idx = op.split()
                idx = int(idx) - 1
                if direction == 'L':
                    row = current_pos[idx * n:(idx + 1) * n]
                    current_pos[idx * n:(idx + 1) * n] = row[1:] + row[:1]
                elif direction == 'R':
                    row = current_pos[idx * n:(idx + 1) * n]
                    current_pos[idx * n:(idx + 1) * n] = row[-1:] + row[:-1]
                elif direction == 'U':
                    col = current_pos[idx::n]
                    current_pos[idx::n] = col[1:] + col[:1]
                elif direction == 'D':
                    col = current_pos[idx::n]
                    current_pos[idx::n] = col[-1:] + col[:-1]
        if current_pos == target_pos:
            return cycle_length % MOD
        cycle_length += 1

# Exemplu de utilizare
n = 4
grid = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]
sequence = ["L 1", "D 2", "R 3", "U 4"]

print(min_operations_to_initial(n, grid, True)) # Operații pe linii
print(min_operations_to_initial(n, grid, False)) # Operații pe coloane
print(min_apply_sequence(n, sequence))
</syntaxhighlight>