RaulOtet: Pagină nouă: Dintr-o suprafaţă pătrată cu latura de `N` unităţi care este formată din `N*N` pătrăţele cu latura de o unitate se decupează cele `4` pătrăţele din colţuri. = Cerința = Determinaţi o modalitate de a acoperi suprafaţa în întregime cu piese de arie `4` unităţi care au forma următoare: Piesele pot fi si rotite sau întoarse putând astfel să folosim toate cele `8` moduri de a le aşeza. = Date de i...

2024-07-31T05:47:36Z

Pagină nouă: Dintr-o suprafaţă pătrată cu latura de <code>N</code> unităţi care este formată din <code>N*N</code> pătrăţele cu latura de o unitate se decupează cele <code>4</code> pătrăţele din colţuri. = Cerința = Determinaţi o modalitate de a acoperi suprafaţa în întregime cu piese de arie <code>4</code> unităţi care au forma următoare: Piesele pot fi si rotite sau întoarse putând astfel să folosim toate cele <code>8</code> moduri de a le aşeza. = Date de i...

New page

Dintr-o suprafaţă pătrată cu latura de <code>N</code> unităţi care este formată din <code>N*N</code> pătrăţele cu latura de o unitate se decupează cele <code>4</code> pătrăţele din colţuri.

= Cerința =
Determinaţi o modalitate de a acoperi suprafaţa în întregime cu piese de arie <code>4</code> unităţi care au forma următoare:

Piesele pot fi si rotite sau întoarse putând astfel să folosim toate cele <code>8</code> moduri de a le aşeza.

= Date de intrare =
Fișierul de intrare <code>acoperire1.in</code> conține pe prima linie un număr natural <code>N</code>, cu semnificaţia din enunţ.

= Date de ieșire =
Fișierul de ieșire <code>acoperire1.out</code> va conține valoarea <code>-1</code> pe prima linie dacă problema nu are soluţie, iar în caz contrar va avea următoarea structură: <code>N</code> linii cu câte <code>N</code> valori fiecare reprezentând codificarea suprafeţei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu. Poziţiile ocupate de prima piesă aşezată se vor codifica cu <code>1</code>, poziţiile ocupate de a doua piesă aşezată se vor codifica cu <code>2</code> etc. Corespunzător colţurilor lipsă se va scrie valoarea <code>0</code>.

= Restricții și precizări =

* <code>6 ≤ n ≤ 200</code>
* Piesele trebuie să fie complet în interiorul zonei;
* Zona trebuie acoperită integral;
* Două piese nu se pot suprapune complet sau parţial;

= Exemplu: =
<code>acoperire1.in</code>
6
<code>acoperire1.out</code>
0 7 2 2 2 0
3 7 2 4 4 4
3 7 7 4 5 5
3 3 6 1 1 5
6 6 6 8 1 5
0 8 8 8 1 0
<syntaxhighlight lang="python" line="1">
def place_l_tiles(board, n, top_left_row, top_left_col):
# n - dimension of the current board (n x n)
if n == 2:
# Base case: only one tile can fit, as 4 cells are considered and one corner is missing
for i in range(2):
for j in range(2):
if board[top_left_row + i][top_left_col + j] == 0:
board[top_left_row + i][top_left_col + j] = 1
return

half = n // 2
# Find the center tile to place the L-shaped tromino around
# (middle of the top-left, top-right, bottom-left, bottom-right quarters)
center_r, center_c = top_left_row + half - 1, top_left_col + half - 1

# Determine which quadrant is missing the corner cell
if board[top_left_row][top_left_col] == -1:
missing_quad = 0
elif board[top_left_row][top_left_col + n - 1] == -1:
missing_quad = 1
elif board[top_left_row + n - 1][top_left_col] == -1:
missing_quad = 2
elif board[top_left_row + n - 1][top_left_col + n - 1] == -1:
missing_quad = 3

# Fill the center of the current board with a L-shaped tromino
tiles = [(center_r, center_c), (center_r, center_c + 1), (center_r + 1, center_c), (center_r + 1, center_c + 1)]
# We have four quadrants (0: top-left, 1: top-right, 2: bottom-left, 3: bottom-right)
for idx, (i, j) in enumerate(tiles):
if idx != missing_quad:
board[i][j] = 1

# Recursively fill each of the four quadrants
# Top-left quadrant
place_l_tiles(board, half, top_left_row, top_left_col)
# Top-right quadrant
place_l_tiles(board, half, top_left_row, top_left_col + half)
# Bottom-left quadrant
place_l_tiles(board, half, top_left_row + half, top_left_col)
# Bottom-right quadrant
place_l_tiles(board, half, top_left_row + half, top_left_col + half)

# Initialize the board
N = 4 # Example value, should be a power of 2
board = [[0 for _ in range(N)] for _ in range(N)]

# Remove corners
board[0][0] = -1
board[0][N-1] = -1
board[N-1][0] = -1
board[N-1][N-1] = -1

# Place L-shaped tiles starting from the top-left corner of the board
place_l_tiles(board, N, 0, 0)

# Print the board
for row in board:
print(' '.join(str(cell) for cell in row))
</syntaxhighlight>

0726 - Acoperire 1 - Revision history