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

<syntaxhighlight lang="python" line>

1. 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

1. 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]

1. Verificarea restricțiilor și calculul rezultatului

shifts = find_shifts(n, config)

1. 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')

</syntaxhighlight>

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.