3651 - Ghem

Se consideră un tablou cu N linii și N coloane ce conține numerele naturale de la 1 la N2 așezate consecutiv, întâi pe linii și apoi pe coloane, începând cu 1 în colțul din stânga sus, conform exemplului alăturat (N = 4).

Dacă se derulează elemente tabloului, asemănător cu un ghem, prin rotirea tabloului în jurul centrului (intersecția diagonalelor), trăgând de unul din colțurile sale pe orizontală sau pe verticală, către exterior, se obține un șir cu numerele de la 1 la N2, într-o anumită ordine.

Exemple: dacă N = 4 și se va trage de:

• colțul din stânga sus – pe orizontală, se va obține șirul: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10;
• colțul din dreapta jos – pe verticală, se va obține șirul: 16 12 8 4 3 2 1 5 9 13 14 15 11 7 6 10;

Cerința

Să se scrie un program care citește:

• un numărul natural N, ce reprezintă numărul de linii și de coloane al unui tablou ce conține numerele naturale de la 1 la N2;
• două numere naturale X și Y, ce reprezintă coordonatele colțului de unde se face derularea: { (1,1) – stânga sus; (1,N) – dreapta sus; (N,N) – dreapta jos; (N,1) – stânga jos;}
• un caracter D (majusculă), ce reprezintă direcția pe care se face tragerea (O – orizontală și V – verticală).

și afișează șirul de numere ce rezultă din desfășurarea tabloului, începând cu colțul de unde se face tragerea și pe

direcția de tragere.

Date de intrare

Fișierul de intrare ghem.in conţine pe prima linie numărul natural N, pe a doua linie două numere naturale X și Y despărțite printr-un spațiu, iar pe a treia linie caracterul D, având semnificația de mai sus.

Date de ieșire

Fișierul de ieșire ghem.out va conţine pe primul rând șirul de numere obținut prin desfășurarea tabloului.

Între oricare două numere succesive va exista un singur spațiu.

Restricții și precizări

• 2 ≤ N ≤ 500• (X,Y) aparține mulțimii {(1,1), (1,N), (N,N), (N,1)}; • D aparține mulțimii {’O’,’V’} – majuscule;

Exemplu:

ghem.in

4
1 1
O

ghem.out

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Explicație

Matricea alăturată se desfășoară “trăgând” de colțul din stânga sus în direcție orizontală obținându-se șirul: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

<syntaxhighlight lang="python" line="1"> def generate_matrix(N):

   matrix = []
   num = 1
   for i in range(N):
       row = []
       for j in range(N):
           row.append(num)
           num += 1
       matrix.append(row)
   return matrix

def spiral_from_top_left(matrix, N):

   result = []
   top, left, bottom, right = 0, 0, N - 1, N - 1
   while top <= bottom and left <= right:
       for i in range(left, right + 1):
           result.append(matrix[top][i])
       top += 1
       for i in range(top, bottom + 1):
           result.append(matrix[i][right])
       right -= 1
       if top <= bottom:
           for i in range(right, left - 1, -1):
               result.append(matrix[bottom][i])
           bottom -= 1
       if left <= right:
           for i in range(bottom, top - 1, -1):
               result.append(matrix[i][left])
           left += 1
   return result

def spiral_from_bottom_right(matrix, N):

   result = []
   bottom, right, top, left = N - 1, N - 1, 0, 0
   while bottom >= top and right >= left:
       for i in range(right, left - 1, -1):
           result.append(matrix[bottom][i])
       bottom -= 1
       for i in range(bottom, top - 1, -1):
           result.append(matrix[i][left])
       left += 1
       if bottom >= top:
           for i in range(left, right + 1):
               result.append(matrix[top][i])
           top += 1
       if right >= left:
           for i in range(top, bottom + 1):
               result.append(matrix[i][right])
           right -= 1
   return result

def spiral_from_top_right(matrix, N):

   result = []
   top, right, bottom, left = 0, N - 1, N - 1, 0
   while top <= bottom and right >= left:
       for i in range(top, bottom + 1):
           result.append(matrix[i][right])
       right -= 1
       for i in range(right, left - 1, -1):
           result.append(matrix[bottom][i])
       bottom -= 1
       if right >= left:
           for i in range(bottom, top - 1, -1):
               result.append(matrix[i][left])
           left += 1
       if top <= bottom:
           for i in range(left, right + 1):
               result.append(matrix[top][i])
           top += 1
   return result

def spiral_from_bottom_left(matrix, N):

   result = []
   bottom, left, top, right = N - 1, 0, 0, N - 1
   while bottom >= top and left <= right:
       for i in range(left, right + 1):
           result.append(matrix[bottom][i])
       bottom -= 1
       for i in range(bottom, top - 1, -1):
           result.append(matrix[i][right])
       right -= 1
       if left <= right:
           for i in range(right, left - 1, -1):
               result.append(matrix[top][i])
           top += 1
       if bottom >= top:
           for i in range(top, bottom + 1):
               result.append(matrix[i][left])
           left += 1
   return result

def get_spiral_order(N, X, Y, D):

   matrix = generate_matrix(N)
   
   if (X, Y) == (1, 1):
       if D == 'O':
           return spiral_from_top_left(matrix, N)
       else:
           return spiral_from_bottom_left(matrix, N)[::-1]
   elif (X, Y) == (1, N):
       if D == 'O':
           return spiral_from_top_right(matrix, N)
       else:
           return spiral_from_top_left(matrix, N)[::-1]
   elif (X, Y) == (N, N):
       if D == 'O':
           return spiral_from_bottom_right(matrix, N)
       else:
           return spiral_from_top_right(matrix, N)[::-1]
   elif (X, Y) == (N, 1):
       if D == 'O':
           return spiral_from_bottom_left(matrix, N)
       else:
           return spiral_from_bottom_right(matrix, N)[::-1]

1. Citirea datelor de intrare

N = int(input()) X = int(input()) Y = int(input()) D = input().strip()

1. Generarea și afișarea șirului de numere

result = get_spiral_order(N, X, Y, D) print(" ".join(map(str, result))) </syntaxhighlight>