UVa 1605 - UN Headquarters 建築設計：兩層矩陣構造解法

前言

UVa 1605 要求為 $n$ 個國家設計最少辦公室的建築，使任意兩國至少有一對相鄰辦公室 (同層共牆或上下樓層同位置)。關鍵洞察：僅需兩層即可滿足所有 $n \le 50$。

構造策略

• 建築高度 $h=2$，寬度 $w=n$，長度 $l=n$ (或 $w=n, l=n$)。
• 第 1 層：第 $i$ 列全為國家 $i$ (字母表示)。
• 第 2 層：第 $j$ 行全為國家 $j$。
• 結果：國家 $i$ 在第 1 層佔據第 $i$ 列 (垂直連通)；在第 2 層佔據第 $i$ 行 (水平連通)。
  任意兩國 $i, j$：在第 1 層第 $i$ 列與第 $j$ 列相鄰 (共牆)；或在第 2 層第 $i$ 行與第 $j$ 行相鄰；或上下樓層同座標 $(i,j)$ 相鄰。保證至少一對相鄰。
• 總辦公室數 $2 \times n \times n \le 2 \times 50 \times 50 = 5000 \ll 1,000,000$ 限制。

完整程式碼

#include 
#include 

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        printf("2 %d %d\n", n, n);
        /* 第 1 層：每列同一國家 */
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i < 26) putchar('A' + i);
                else        putchar('a' + i - 26);
            }
            putchar('\n');
        }
        putchar('\n');  /* 層間空行 */
        /* 第 2 層：每行同一國家 */
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j < 26) putchar('A' + j);
                else        putchar('a' + j - 26);
            }
            putchar('\n');
        }
        putchar('\n');  /* 測資間空行 */
    }
    return 0;
}

輸出範例 (n=4)

2 4 4
AAAA
BBBB
CCCC
DDDD

ABCD
ABCD
ABCD
ABCD

關鍵點

• 字母超過 26 續用小寫 `a`~`z` (題目允許大小寫)。
• 層之間、測資之間各輸出一空行。
• 構造證明：任意 $i \neq j$，國家 $i$ 在第 1 層第 $i$ 列與國家 $j$ 第 $j$ 列相鄰；或第 2 層第 $i$ 行與第 $j$ 行相鄰；或座標 $(i,j)$ 上下樓層分屬 $i,j$ 相鄰。