Oros Ioana Diana: Pagină nouă: 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 nn brioşe au fost numerotate de la 1 la nn, 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 l...

2024-01-08T23:52:14Z

Pagină nouă: 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 l...

New page

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
<br>
== 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
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#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')

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

0150 - Shift 1 - Revision history