Editing 3574 - Perspic

Se consideră o matrice pătratică cu <code>N</code> linii şi <code>N</code> coloane ce conţine toate numerele naturale de la <code>1</code> la <code>N*N</code>.

Asupra matricei se definesc trei tipuri de operaţii codificate astfel:

* <code>C i j</code> – interschimbarea coloanelor <code>i</code> şi <code>j</code> ale matricei
* <code>R i j</code> – interschimbarea liniilor <code>i</code> şi <code>j</code> ale matricei
* <code>E i j x y</code> – interschimbarea elementului de pe linia <code>i</code> şi coloana <code>j</code> cu elementul de pe linia <code>x</code> şi coloana <code>y</code>.

Asupra matricei se efectuează un set de <code>M</code> astfel de operaţii.

= Cerința =
Se cere să se determine numărul minim de aplicări complete ale acestui set de operaţii după care se ajunge din nou în starea iniţială. În cadrul setului operaţiile se efectuează mereu în aceeaşi ordine şi nu se poate sări peste o operaţie. Deoarece numărul acesta poate fi foarte mare se cere restul împărţirii sale la <code>13007</code>.

= Date de intrare =
Fişierul de intrare <code>perspic.in</code> conţine pe prima linie numerele naturale <code>N</code> şi <code>M</code>, separate printr-un spaţiu, reprezentând dimensiunea matricei şi respectiv numărul de operaţii dintr-un set. Pe următoarele <code>M</code> linii se descriu operaţiile setului.

= Date de ieșire =
Fişierul de ieşire <code>perspic.out</code> va conţine restul împărţirii la <code>13007</code> al numărului minim determinat.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100</code>
* <code>1 ≤ M ≤ 10.000</code>
* Pentru <code>60%</code> din teste numărul minim de aplicări ale setului de operaţii necesare va fi mai mic ca <code>2.000.000.000</code>.

= Exemplu: =
<code>perspic.in</code>
 2 2
 C 1 2
 R 1 2
<code>perspic.out</code>
 2
<syntaxhighlight lang="python" line="1">
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def find_cycles(permutation):
    visited = [False] * len(permutation)
    cycles = []
    for i in range(len(permutation)):
        if not visited[i]:
            cycle_length = 0
            x = i
            while not visited[x]:
                visited[x] = True
                x = permutation[x]
                cycle_length += 1
            cycles.append(cycle_length)
    return cycles

def main():
    import sys
    input = sys.stdin.read
    data = input().strip().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    permutation = list(range(N * N))
    
    for _ in range(M):
        operation = data[idx]
        if operation == 'C':
            i = int(data[idx + 1]) - 1
            j = int(data[idx + 2]) - 1
            idx += 3
            for row in range(N):
                permutation[row * N + i], permutation[row * N + j] = permutation[row * N + j], permutation[row * N + i]
        elif operation == 'R':
            i = int(data[idx + 1]) - 1
            j = int(data[idx + 2]) - 1
            idx += 3
            for col in range(N):
                permutation[i * N + col], permutation[j * N + col] = permutation[j * N + col], permutation[i * N + col]
        elif operation == 'E':
            i = int(data[idx + 1]) - 1
            j = int(data[idx + 2]) - 1
            x = int(data[idx + 3]) - 1
            y = int(data[idx + 4]) - 1
            idx += 5
            permutation[i * N + j], permutation[x * N + y] = permutation[x * N + y], permutation[i * N + j]
    
    cycles = find_cycles(permutation)
    result = 1
    for cycle_length in cycles:
        result = lcm(result, cycle_length)
    
    print(result % 13007)

if __name__ == "__main__":
    main()
</syntaxhighlight>