Editing 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 <code>n x n</code> celule, în care atât rândurile cât și coloanele sunt numerotate de la <code>1</code>;
* În starea inițială a tabelei, în fiecare celulă se află câte un număr de la <code>1</code> la <code>n^2</code>, astfel încât <code>M[i,j] = (i - 1) * n + j</code>
* Asupra tabelei se pot aplica patru tipuri de operații de oricâte ori:

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

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

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

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

= 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 <code>m</code> operații, care este numărul minim de aplicări ale acestei secvențe asupra unei tabele de dimensiune <code>n x n</code> 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 <code>1.000.000.007</code>.

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

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

= Date de ieșire =
În fișierul <code>loopover.out</code> se va afișa în funcție de cerință:

* dacă <code>t = 1</code>, un singur număr reprezentând numărul minim de operații pentru a aduce tabela în starea inițială.
* dacă <code>t = 2</code>, un singur număr reprezentând restul împărțirii la <code>1.000.000.007</code> 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 =

* <code>2 ≤ n ≤ 1000</code>
* <code>1 ≤ m ≤ 1000</code>
* <code>t ∈ {1, 2}</code>
* <code>1 ≤ x<sub>i</sub></code> <code>≤ n</code> pentru orice <code>1 ≤ i ≤ m</code>

= Exemplul 1: =
<code>loopover.in</code>
 1 4
 2 3 4 1
 8 5 6 7
 11 12 9 10
 13 14 15 16
<code>loopover.out</code>
 4

=== Explicație ===
Operațiile ce trebuie aplicate sunt:

<code>R 1</code>

<code>L 2</code>

<code>L 3</code>

<code>L 3</code>

= Exemplul 2: =
<code>loopover.in</code>
 1 3
 7 8 6
 1 2 9
 4 5 3
<code>loopover.out</code>
 3

=== Explicație ===
Operațiile ce trebuie aplicate sunt:

<code>U 1</code>

<code>U 2</code>

<code>D 3</code>

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

=== Explicație ===
După aplicarea secvenței de <code>5</code> operații, matricea obținută de Baxibilian este:

<code>2 3 5</code>

<code>8 6 7</code>

<code>1 4 9</code>

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

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