結果
| 問題 |
No.223 1マス指定の魔方陣
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:06:52 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,358 bytes |
| コンパイル時間 | 295 ms |
| コンパイル使用メモリ | 82,668 KB |
| 実行使用メモリ | 56,044 KB |
| 最終ジャッジ日時 | 2025-05-14 13:08:27 |
| 合計ジャッジ時間 | 3,942 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 23 WA * 23 |
ソースコード
import sys
# Function to solve the problem
def solve():
# Read input N, X, Y, Z
N, X, Y, Z = map(int, sys.stdin.readline().split())
# Adjust coordinates to 0-based indexing for internal use
# The problem uses 1-based indexing (1 to N)
# Python uses 0-based indexing (0 to N-1)
target_Y = Y - 1
target_X = X - 1
# Standard Magic Square Construction for Doubly Even Order N (N = 4k)
# This method applies when N is a multiple of 4. Here N is 4, 8, or 16.
# Step 1: Create a grid 'grid_A' filled sequentially with numbers from 1 to N^2
grid_A = [[0]*N for _ in range(N)]
for r in range(N):
for c in range(N):
# Calculate value using 0-based indices r, c
grid_A[r][c] = r * N + c + 1
# Step 2: Create the magic square grid 'grid_B' based on a marking pattern
# The value in grid_B is either the value from grid_A or its complement (N^2 + 1 - value).
grid_B = [[0]*N for _ in range(N)]
N2_plus_1 = N*N + 1 # The sum of complementary pairs
# Define the marking pattern based on modulo 4 properties of coordinates
for r in range(N):
for c in range(N):
# Get coordinates modulo 4
r_mod_4 = r % 4
c_mod_4 = c % 4
# Determine if the cell (r, c) should be marked based on the standard rule for N=4k squares.
# Rule: A cell (r, c) is marked if (r mod 4 is 0 or 3) iff (c mod 4 is 0 or 3).
# This can be simplified: The condition (r mod 4 in {0, 3}) must have the same truth value
# as the condition (c mod 4 in {0, 3}).
# Condition 1: r mod 4 is 0 or 3
cond1 = (r_mod_4 == 0 or r_mod_4 == 3)
# Condition 2: c mod 4 is 0 or 3
cond2 = (c_mod_4 == 0 or c_mod_4 == 3)
# A cell is marked if cond1 and cond2 are both true, OR if cond1 and cond2 are both false.
# This is equivalent to checking if cond1 == cond2.
marked = (cond1 == cond2)
if marked:
# If marked, use the complementary value N^2 + 1 - A[r][c]
grid_B[r][c] = N2_plus_1 - grid_A[r][c]
else:
# If not marked, use the original value A[r][c]
grid_B[r][c] = grid_A[r][c]
# The generated grid_B is the standard magic square, let's call it S.
S = grid_B
# Define row/column permutations that swap indices i with i + N/2 (modulo N).
# These permutations are known to preserve the magic square property for squares constructed
# using this standard method for doubly even N.
# Function to permute rows: row i goes to row (i + N/2) % N
def permute_rows(grid):
new_grid = [[0]*N for _ in range(N)]
k = N // 2 # N is guaranteed to be even
for r in range(N):
# Calculate the target row index after permutation
new_r = (r + k) % N
# Copy the entire row r from the original grid to row new_r in the new grid
for c in range(N):
new_grid[new_r][c] = grid[r][c]
return new_grid
# Function to permute columns: column j goes to column (j + N/2) % N
def permute_cols(grid):
new_grid = [[0]*N for _ in range(N)]
k = N // 2
for r in range(N):
for c in range(N):
# Calculate the target column index after permutation
new_c = (c + k) % N
# Copy the element grid[r][c] to the new column position new_c in the new grid
new_grid[r][new_c] = grid[r][c]
return new_grid
# Generate 4 base squares by applying combinations of these row/column permutations.
# It's known that these transformations generate potentially different magic squares.
base_squares = []
base_squares.append(S) # Base case: The original standard square S.
S_perm_cols = permute_cols(S)
base_squares.append(S_perm_cols) # Apply column permutation only.
S_perm_rows = permute_rows(S)
base_squares.append(S_perm_rows) # Apply row permutation only.
# Apply column permutation to the row-permuted square. Order doesn't matter.
S_perm_both = permute_cols(S_perm_rows)
base_squares.append(S_perm_both) # Apply both row and column permutations.
# Define 8 symmetry operations (Identity, Rotations, Reflections)
# These operations also preserve the magic square property.
# Function to return an identical copy of the grid.
def identity(grid):
# Return a deep copy to avoid modifying the original grid when transformations are applied.
return [row[:] for row in grid]
# Function to rotate the grid 90 degrees clockwise.
def rotate90(grid):
new_grid = [[0]*N for _ in range(N)]
for r in range(N):
for c in range(N):
# Element at (r, c) moves to (c, N-1-r)
new_grid[c][N-1-r] = grid[r][c]
return new_grid
# Function to rotate the grid 180 degrees.
def rotate180(grid):
new_grid = [[0]*N for _ in range(N)]
for r in range(N):
for c in range(N):
# Element at (r, c) moves to (N-1-r, N-1-c)
new_grid[N-1-r][N-1-c] = grid[r][c]
return new_grid
# Function to rotate the grid 270 degrees clockwise (or 90 degrees counter-clockwise).
def rotate270(grid):
new_grid = [[0]*N for _ in range(N)]
for r in range(N):
for c in range(N):
# Element at (r, c) moves to (N-1-c, r)
new_grid[N-1-c][r] = grid[r][c]
return new_grid
# Function to reflect the grid horizontally (across the middle horizontal axis).
def reflect_h(grid):
new_grid = [[0]*N for _ in range(N)]
for r in range(N):
for c in range(N):
# Element at (r, c) moves to (N-1-r, c)
new_grid[N-1-r][c] = grid[r][c]
return new_grid
# Function to reflect the grid vertically (across the middle vertical axis).
def reflect_v(grid):
new_grid = [[0]*N for _ in range(N)]
for r in range(N):
for c in range(N):
# Element at (r, c) moves to (r, N-1-c)
new_grid[r][N-1-c] = grid[r][c]
return new_grid
# Function to reflect the grid across the main diagonal (top-left to bottom-right).
def reflect_d1(grid):
new_grid = [[0]*N for _ in range(N)]
for r in range(N):
for c in range(N):
# Element at (r, c) moves to (c, r) (Transpose)
new_grid[c][r] = grid[r][c]
return new_grid
# Function to reflect the grid across the anti-diagonal (top-right to bottom-left).
def reflect_d2(grid):
new_grid = [[0]*N for _ in range(N)]
for r in range(N):
for c in range(N):
# Element at (r, c) moves to (N-1-c, N-1-r)
new_grid[N-1-c][N-1-r] = grid[r][c]
return new_grid
# List containing all 8 symmetry functions.
symmetries = [
identity, rotate90, rotate180, rotate270,
reflect_h, reflect_v, reflect_d1, reflect_d2
]
# Iterate through the 4 base squares generated earlier.
# For each base square, apply each of the 8 symmetry operations.
# This gives a total of 4 * 8 = 32 candidate magic squares.
# The problem guarantees that at least one solution exists, so one of these candidates must work.
for base_sq in base_squares:
for sym_func in symmetries:
# Apply the symmetry function to the current base square.
transformed_sq = sym_func(base_sq)
# Check if the value at the target cell (target_Y, target_X) in the transformed square matches the required value Z.
if transformed_sq[target_Y][target_X] == Z:
# If it matches, we have found the required magic square.
# Print the square row by row, with elements separated by spaces.
for r in range(N):
print(*(transformed_sq[r]))
# Exit the function since we found and printed the solution.
return
# Call the main function to solve the problem.
solve()