結果
問題 |
No.2339 Factorial Paths
|
ユーザー |
![]() |
提出日時 | 2025-05-14 13:11:06 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,315 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 82,764 KB |
実行使用メモリ | 62,332 KB |
最終ジャッジ日時 | 2025-05-14 13:13:12 |
合計ジャッジ時間 | 4,864 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 1 WA * 19 |
ソースコード
import sys def solve(): # Read input N N = int(sys.stdin.readline()) # Handle base cases for N=1, N=2, N=3 based on sample outputs and simple logic if N == 1: # The sample output for N=1 provides a specific 3x4 grid. # Let's verify the path count manually: # Grid: # ..## # #..# # ##.. # Paths P(i,j): # R1: 1 1 0 0 # R2: 0 1 1 0 (P(2,1)=0, P(2,2)=P(1,2)+P(2,1)=1+0=1, P(2,3)=P(1,3)+P(2,2)=0+1=1, P(2,4)=0) # R3: 0 0 1 1 (P(3,1)=0, P(3,2)=0, P(3,3)=P(2,3)+P(3,2)=1+0=1, P(3,4)=P(2,4)+P(3,3)=0+1=1) # The number of paths to (3,4) is indeed 1 = 1!. print(3, 4) print("..##") print("#..#") print("##..") return if N == 2: # For N=2, we need 2! = 2 paths. # A simple 2x2 all white grid works: # Grid: # .. # .. # Paths P(i,j): # R1: 1 1 # R2: 1 2 (P(2,1)=P(1,1)=1, P(2,2)=P(1,2)+P(2,1)=1+1=2) # The number of paths to (2,2) is 2. print(2, 2) print("..") print("..") return if N == 3: # For N=3, we need 3! = 6 paths. # The sample output for N=3 provides a 3x3 all white grid. # Grid: # ... # ... # ... # The number of paths in an all-white HxW grid is C(H+W-2, H-1). # For H=3, W=3, paths = C(3+3-2, 3-1) = C(4, 2) = 6. # This matches 3! = 6. print(3, 3) print("...") print("...") print("...") return # For N >= 4, we use a pattern derived from the N=5 sample output. # The N=5 sample output uses a 6x6 grid (H=N+1, W=N+1). # The black cells are at (1,5), (3,3), (5,1). # This matches the pattern: cells (r, c) are black if r is odd (r = 2k-1) # and they lie on the anti-diagonal r + c = N + 2 (using 1-based indexing). # The row index r = 2k-1 must be <= H=N+1. 2k-1 <= N+1 => 2k <= N+2 => k <= (N+2)/2. # Since k must be integer, k <= floor((N+2)/2). # However, the number of black cells in N=5 example is 3, which is floor((5+1)/2) = 3. # So the range for k seems to be 1 to floor((N+1)/2). H = N + 1 W = N + 1 # Initialize grid with all white cells ('.') grid = [['.' for _ in range(W)] for _ in range(H)] # Place black cells ('#') according to the derived pattern # Black cells at row 2k-1 and column N - (2k-1) + 1 # for k = 1 to floor((N+1)/2) # The k-th black cell (1-based index) is at: # Row r_abs = 2 * k - 1 # Column c_abs = N - (2 * k - 1) + 1 # This formula correctly generates (1,5), (3,3), (5,1) for N=5. for k in range(1, (N + 1) // 2 + 1): r_abs = 2 * k - 1 # 1-based row index c_abs = N - (2 * k - 1) + 1 # 1-based col index # Convert to 0-based indices for array access r_idx = r_abs - 1 c_idx = c_abs - 1 # Check bounds just in case, though formula should be correct for N>=4 if 0 <= r_idx < H and 0 <= c_idx < W: grid[r_idx][c_idx] = '#' # Print the grid dimensions print(H, W) # Print the grid row by row for r in range(H): print("".join(grid[r])) # Call the solve function to execute the logic solve()