0150 - Shift 1

Bulbuka este foarte pasionată de gătit deserturi. Ea a decis să facă (n+2)*(n+2) brioşe pe care le-a numerotat (cu ciocolată, bineinţeles) în modul următor: primele n*n brioşe au fost numerotate de la 1 la n*n, iar restul până la (n+2)*(n+2) au primit valoarea 0. De asemenea, după ce au fost gata, Bulbuka nu a putut rezista tentaţiei de a ordona brioşele într-un pătrat cu latura (n+2) după cum urmează: cele cu 0 pe conturul exterior iar cele numerotate de la 1 la n*n, în interior, în ordine crescătoare, pe linii, de sus in jos, ca în figura alăturată. Bulbuka a numit această aranjare configuraţia ordonată a brioşelor.

Acest aranjament frumos a durat foarte puţin deoarece, pe când Bulbuka stătea cu spatele, Randomel a amestecat brioşele între ele, într-o ordine aleatoare. Când s-a întors şi a văzut fapta, ea s-a supărat foarte tare şi l-a pedepsit pe Randomel punându-l să le aranjeze la loc cum erau (ca în imagine) folosind doar un set limitat de operaţii: shiftări circulare pe linii şi pe coloane. O shiftare presupune deplasarea circulară la dreapta, pe linie sau în jos, pe coloană, cu cel puţin una şi cel mult n+1 poziţii.

Cerința

Randomel vă roagă să scrieţi un program care, pentru o aranjare aleatorie a brioşelor, să afişeze shiftările circulare posibile care transformă configuraţia dată într-o configuraţie ordonată.

Date de intrare

Pe prima linie a fişierului de intrare shift1in.txt se află numărul natural n. Pe următoarele n+2 linii se află câte n+2 numere naturale reprezentând elementele configuraţiei date.

Date de ieșire

Fişierul de ieşire shift1out.txt va conţine pe prima linie k, numărul de shiftări necesare. Pe următoarele k linii se vor scrie shiftările făcute, câte o operaţie pe o linie. O shiftare este descrisă astfel: litera L (linie) sau C (coloana) pe care s-a efectuat operaţia, indicele liniei/coloanei şi numărul de brioşe deplasate, separate prin câte un spaţiu

Restricții și precizări

• 1 ≤ N ≤ 500
• Se vor accepta numai soluţii în care numărul de mutări este mai mic decât 1234567
• Numerotarea liniilor/coloanelor începe de la 0

Exemplul 1

shift1in.txt

3

0 0 0 4 0

0 0 2 9 0

0 1 5 6 0

0 0 8 0 0

0 7 0 3 0

shift1out.txt

4

C 1 4

L 2 2

C 3 2

L 2 3

Exemplul 2

shift1in.txt

4

0 0 0 0 0

0 0 0 0 0

0 1 3 4 0

0 0 0 0 0

0 7 0 8 0

shift1out.txt

2

L 2 2

C 4 1

Rezolvare

#0150 - Shift 1
def find_shifts(n, config):
    if not (1 <= n <= 500):
        print("Fals")
        return []

    shifts = []

    # Identificăm poziția 0-urilor pe marginea exterioară
    zero_positions = []
    for i in range(n + 2):
        for j in range(n + 2):
            if config[i][j] == 0:
                zero_positions.append((i, j))

    # Shiftăm 0-urile pe marginea superioară
    for j in range(n + 2):
        target_row = 0
        while zero_positions[j][0] != target_row:
            shifts.append(('L', zero_positions[j][0], 1))
            target_row += 1

    # Shiftăm 0-urile pe marginea dreaptă
    for i in range(1, n + 2):
        target_col = n + 1
        while zero_positions[i][1] != target_col:
            shifts.append(('C', zero_positions[i][1], 1))
            target_col -= 1

    return shifts

# Citirea datelor de intrare
with open("shift1in.txt", "r") as infile:
    n = int(infile.readline())
    config = [list(map(int, line.split())) for line in infile]

# Verificarea restricțiilor și calculul rezultatului
shifts = find_shifts(n, config)

# Scrierea rezultatului în fișierul de ieșire
if shifts:
    with open("shift1out.txt", "w") as outfile:
        outfile.write(str(len(shifts)) + '\n')
        for shift in shifts:
            outfile.write(' '.join(map(str, shift)) + '\n')

Explicatie

Coloana cu indicele 1 se va shifta circular în jos cu 4 poziţii, apoi linia 2 se shiftează circular la dreapta cu 2 poziţii etc.