a226. F. 拼拼圖 - YUTEH ZeroJudge

內容

2022 網際網路程式設計全國大賽國中組決賽

（註：影印題本上的圖片是黑白的，但可於 Kattis 系統上看到彩色的圖片。）

給定一個大小為 N 的正六邊形棋盤，請用指定形狀的拼圖把它填滿。

棋盤

首先我們定義大小為 2 的棋盤如下：

其中畫上 X 的格子是挖空的，上面不能放拼圖。

接著我們定義大小為 N (N ≥ 3) 的棋盤，它可以用以下方法得出：

放置一個大小為 N − 1 的棋盤
將此棋盤的外圍多圍一圈正六邊形

舉例來說，下圖顯示了大小分別為 3 與 4 的棋盤：

特別的是，大小為 N 的棋盤共有 3N²− 3N 個正六邊形（去掉正中間的格子）。拼圖

拼圖的形狀如下，拼圖可以翻轉或旋轉，但不能改變拼圖的形狀。

填滿

填滿一個棋盤需滿足以下條件：

棋盤的每一個正六邊形都被恰一塊拼圖覆蓋，特別注意正中間挖空的格子不能被任一塊拼圖覆蓋
沒有一塊拼圖超出棋盤範圍

以大小為 2 的棋盤為例，下圖說明了一些填滿與未填滿的例子：

上圖中，最左邊是一個填滿的例子，其餘兩個都是未填滿的。中間的原因是正中間挖空的格子有被拼圖覆蓋，而右邊的原因是有兩塊拼圖超出了棋盤範圍。

由於一塊拼圖共包含 3 個正六邊形，因此可以得出一個結論：填滿一個大小為 N 的棋盤共需要 N²− N 塊拼圖。而且可以證明任意大小的棋盤都能被這種形狀的拼圖填滿。

座標

為了能夠表示出放置拼圖的位置，我們定義了正六邊形棋盤的座標系統。我們將棋盤的正中心設為原點 (0,0)，將 3 點鐘方向定為 x 軸正向，1 點鐘方向定為 y 軸正向，如左下圖。而一個六邊形為一單位，這樣我們就可以推出每一個正六邊形格子的座標，如右下圖：

輸入說明

輸入第一行有一個正整數 N，代表六邊形棋盤的大小。

2 ≤ N ≤ 100

輸出說明

請輸出 N²− N 行，第 i 行有六個整數 x_i,₁,y_i,₁,x_i,₂,y_i,₂,x_i,₃,y_i,₃，代表第 i 塊拼圖會被放置在座標 (xi,1,yi,1),(xi,2,yi,2),(xi,3,yi,3) 的位置。

範例輸入

範例輸出

-1 2 -2 2 -2 1
0 2 0 1 -1 1
1 1 2 0 2 -1
1 0 1 -1 2 -2
-2 0 -1 0 0 -1
-1 -1 0 -2 1 -2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (1%): 1.0s , <1K
公開測資點#1 (1%): 1.0s , <1K
公開測資點#2 (1%): 1.0s , <1K
公開測資點#3 (1%): 1.0s , <1K
公開測資點#4 (1%): 1.0s , <1K
公開測資點#5 (1%): 1.0s , <1K
公開測資點#6 (1%): 1.0s , <1K
公開測資點#7 (1%): 1.0s , <1K
公開測資點#8 (1%): 1.0s , <1K
公開測資點#9 (1%): 1.0s , <1K
公開測資點#10 (1%): 1.0s , <1K
公開測資點#11 (1%): 1.0s , <1K
公開測資點#12 (1%): 1.0s , <1K
公開測資點#13 (1%): 1.0s , <1K
公開測資點#14 (1%): 1.0s , <1K
公開測資點#15 (1%): 1.0s , <1K
公開測資點#16 (1%): 1.0s , <1K
公開測資點#17 (1%): 1.0s , <1K
公開測資點#18 (1%): 1.0s , <1K
公開測資點#19 (1%): 1.0s , <1K
公開測資點#20 (1%): 1.0s , <1K
公開測資點#21 (1%): 1.0s , <1K
公開測資點#22 (1%): 1.0s , <1K
公開測資點#23 (1%): 1.0s , <1K
公開測資點#24 (1%): 1.0s , <1K
公開測資點#25 (1%): 1.0s , <1K
公開測資點#26 (1%): 1.0s , <1K
公開測資點#27 (1%): 1.0s , <1K
公開測資點#28 (1%): 1.0s , <1K
公開測資點#29 (1%): 1.0s , <1K
公開測資點#30 (1%): 1.0s , <1K
公開測資點#31 (1%): 1.0s , <1K
公開測資點#32 (1%): 1.0s , <1K
公開測資點#33 (1%): 1.0s , <1K
公開測資點#34 (1%): 1.0s , <1K
公開測資點#35 (1%): 1.0s , <1K
公開測資點#36 (1%): 1.0s , <1K
公開測資點#37 (1%): 1.0s , <1K
公開測資點#38 (1%): 1.0s , <1K
公開測資點#39 (1%): 1.0s , <1K
公開測資點#40 (1%): 1.0s , <1K
公開測資點#41 (1%): 1.0s , <1K
公開測資點#42 (1%): 1.0s , <1K
公開測資點#43 (1%): 1.0s , <1K
公開測資點#44 (1%): 1.0s , <1K
公開測資點#45 (1%): 1.0s , <1K
公開測資點#46 (1%): 1.0s , <1K
公開測資點#47 (1%): 1.0s , <1K
公開測資點#48 (1%): 1.0s , <1K
公開測資點#49 (1%): 1.0s , <1K
公開測資點#50 (1%): 1.0s , <1K
公開測資點#51 (1%): 1.0s , <1K
公開測資點#52 (1%): 1.0s , <1K
公開測資點#53 (1%): 1.0s , <1K
公開測資點#54 (1%): 1.0s , <1K
公開測資點#55 (1%): 1.0s , <1K
公開測資點#56 (1%): 1.0s , <1K
公開測資點#57 (1%): 1.0s , <1K
公開測資點#58 (1%): 1.0s , <1K
公開測資點#59 (1%): 1.0s , <1K
公開測資點#60 (1%): 1.0s , <1K
公開測資點#61 (1%): 1.0s , <1K
公開測資點#62 (1%): 1.0s , <1K
公開測資點#63 (1%): 1.0s , <1K
公開測資點#64 (1%): 1.0s , <1K
公開測資點#65 (1%): 1.0s , <1K
公開測資點#66 (1%): 1.0s , <1K
公開測資點#67 (1%): 1.0s , <1K
公開測資點#68 (1%): 1.0s , <1K
公開測資點#69 (1%): 1.0s , <1K
公開測資點#70 (1%): 1.0s , <1K
公開測資點#71 (1%): 1.0s , <1K
公開測資點#72 (1%): 1.0s , <1K
公開測資點#73 (1%): 1.0s , <1K
公開測資點#74 (1%): 1.0s , <1K
公開測資點#75 (1%): 1.0s , <1K
公開測資點#76 (1%): 1.0s , <1K
公開測資點#77 (1%): 1.0s , <1K
公開測資點#78 (1%): 1.0s , <1K
公開測資點#79 (1%): 1.0s , <1K
公開測資點#80 (1%): 1.0s , <1K
公開測資點#81 (1%): 1.0s , <1K
公開測資點#82 (1%): 1.0s , <1K
公開測資點#83 (1%): 1.0s , <1K
公開測資點#84 (1%): 1.0s , <1K
公開測資點#85 (1%): 1.0s , <1K
公開測資點#86 (1%): 1.0s , <1K
公開測資點#87 (1%): 1.0s , <1K
公開測資點#88 (1%): 1.0s , <1K
公開測資點#89 (1%): 1.0s , <1K
公開測資點#90 (1%): 1.0s , <1K
公開測資點#91 (1%): 1.0s , <1K
公開測資點#92 (1%): 1.0s , <1K
公開測資點#93 (1%): 1.0s , <1K
公開測資點#94 (1%): 1.0s , <1K
公開測資點#95 (1%): 1.0s , <1K
公開測資點#96 (1%): 1.0s , <1K
公開測資點#97 (1%): 1.0s , <1K
公開測資點#98 (2%): 1.0s , <1K

提示：

上圖顯示了棋盤大小分別為 2,3,4 的答案，同時你可以運用下方的巨大棋盤幫助你思考。

標籤:

2022國中組決賽

出處:

NPSC [管理者：

zero (管理員)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」