4171 - Loop Over

Baxibilian în timp ce învață la informatică a descoperit jocul Loopover. Acest joc poate fi descris prin următoarele reguli:

• Jocul se desfășoară pe o tabelă pătratică de n x n celule, în care atât rândurile cât și coloanele sunt numerotate de la 1;
• În starea inițială a tabelei, în fiecare celulă se află câte un număr de la 1 la n^2, astfel încât M[i,j] = (i - 1) * n + j
• Asupra tabelei se pot aplica patru tipuri de operații de oricâte ori:

- L x – Toate valorile din celulele de pe linia x se vor deplasa ciclic la stânga cu o unitate, adică M[x,i] = M[x,i+1] pentru i < n și M[x,n] = M[x,1]

- R x – Toate valorile din celulele de pe linia x se vor deplasa ciclic la dreapta cu o unitate, adică M[x,i] = M[x,i-1] pentru i > 1 și M[x,1] = M[x,n]

- U x – Toate valorile din celulele de pe coloana x se vor deplasa ciclic în sus cu o unitate, adică M[i,x] = M[i+1,x] pentru i < n și M[n,x] = M[1,x]

- D x – Toate valorile din celulele de pe coloana x se vor deplasa ciclic în jos cu o unitate, adică M[i,x] = M[i-1,x] pentru i > 1 și M[1,x] = M[n,x]

Cerința

Cum Baxibilian nu are timp să analizeze prea mult jocul Loopover, deoarece are de învățat, el dorește să știe următoarele lucruri:

• Fiind dată starea unei tabele asupra căreia s-au făcut fie doar operații asupra liniilor, fie doar operații asupra coloanelor, care este numărul minim de operații pe care Baxibilian ar trebui să le aplice pentru a reveni în starea inițială?
• Fiind dată o secvență de m operații, care este numărul minim de aplicări ale acestei secvențe asupra unei tabele de dimensiune n x n aflate în starea inițială astfel încât starea finală să fie aceeași ca starea inițială? Întrucât rezultatul poate fi un număr foarte mare, Baxibilian este mulțumit dacă află doar restul împărțirii acestui număr la 1.000.000.007.

Date de intrare

De pe prima linie a fișierului loopover.in se vor afla două numere separate printr-un spațiu t cerința care trebuie rezolvată și n dimensiunea tabelei. În continuare:

• Dacă t = 1, pe următoarele n linii se vor afla, câte n numere separate prin câte un spațiu, reprezentând configurația tabelei.
• Dacă t = 2, pe ce-a de-a doua linie se va afla un singur număr m, iar pe următoarele m linii se vor afla, separate prin câte un spațiu, un caracter ci ∈ {L,R,U,D} reprezentând tipul operației și un număr xi reprezentând indexul liniei sau coloanei asupra căreia se aplică operația i.

Date de ieșire

În fișierul loopover.out se va afișa în funcție de cerință:

• dacă t = 1, un singur număr reprezentând numărul minim de operații pentru a aduce tabela în starea inițială.
• dacă t = 2, un singur număr reprezentând restul împărțirii la 1.000.000.007 al numărului minim de aplicări ale secvenței de operații asupra tabelei pentru ca aceasta să ajungă înapoi în starea inițială.

Restricții și precizări

• 2 ≤ n ≤ 1000
• 1 ≤ m ≤ 1000
• t ∈ {1, 2}
• 1 ≤ xi ≤ n pentru orice 1 ≤ i ≤ m

Exemplul 1:

loopover.in

1 4
2 3 4 1
8 5 6 7
11 12 9 10
13 14 15 16

loopover.out

4

Explicație

Operațiile ce trebuie aplicate sunt:

R 1

L 2

L 3

L 3

Exemplul 2:

loopover.in

1 3
7 8 6
1 2 9
4 5 3

loopover.out

3

Explicație

Operațiile ce trebuie aplicate sunt:

U 1

U 2

D 3

Exemplul 3:

loopover.in

2 3
5
U 1
R 1
U 2
R 1
L 2

loopover.out

6

Explicație

După aplicarea secvenței de 5 operații, matricea obținută de Baxibilian este:

2 3 5

8 6 7

1 4 9

Numărul minim de aplicări ale secvenței pentru a ajunge la matricea identitate este 6.

Exemplul 4:

loopover.in

2 8
10
R 6
L 8
R 4
U 3
L 3
L 1
R 3
U 5
U 6
U 3

loopover.out

4284

Explicație

Sunt necesare 4284 de aplicări ale secvenței pentru a reveni în starea inițială.

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