扎 根 計 畫 高 中 職 - 05 學 年 度 飆 程 式 網 線 上 解 題 活 動 個 人 組 與 團 體 組 活 動 規 則 暨 第 一 階 段 試 題 公 告 06..0 一 活 動 說 明. 本 解 題 活 動 宗 旨 乃 在 協 助 高 中 職 學 生 發 展 程 式 邏 輯, 藉 由 學 生 撰 寫 程 式 的 經 驗 提 昇 程 式 設 計 的 能 力, 盼 能 為 國 家 軟 體 工 業 的 發 展 有 所 幫 助, 由 樹 德 科 技 大 學 和 高 雄 市 復 華 中 學 共 同 建 置. 本 解 題 系 統 網 站 為 :http://khcode.m-school.tw/. 本 解 題 活 動 網 站 為 :http://kh-coding.blogspot.tw/. 本 活 動 分 為 個 人 組 與 團 體 組, 為 提 供 學 生 充 分 討 論 與 解 題 的 機 會, 試 題 分 為 三 階 段 公 布 第 一 階 段 試 題 於 06 年 月 日 公 布 ; 第 二 階 段 試 題 於 06 年 月 8 日 公 布 ; 第 三 階 段 試 題 於 06 年 月 日 公 布 預 計 於 月 7 日 止 停 止 傳 送 5. 於 題 目 公 布 後, 擇 期 公 布 即 時 計 分 板 6. 於 公 布 隔 日 開 放 上 傳 答 案 7. 個 人 組 採 等 級 頒 發 設 計, 等 級 頒 發 標 準 如 下 所 示 設 報 名 同 學 於 第 一 級 至 第 五 級 得 分 分 別 為 SS, SS, SS, SS, SS 5, 則 達 成 該 對 應 條 件 即 可 獲 頒 該 級 數 之 證 書 : 第 一 級 :SS + (SS + SS + SS + SS 5 ) 800 第 二 級 :SS + (SS + SS + SS 5 ) 800 第 三 級 :SS + (SS + SS 5 ) 800 第 四 級 :SS + SS 5 800 第 五 級 :SS + SS 5 800 且 SS 5 600 8. 團 體 組 採 團 體 計 分, 共 有 三 個 題 組, 每 個 題 組 有 若 干 題 目, 其 得 分 加 總 計 算 9. 本 解 題 活 動 鼓 勵 自 由 討 論, 但 個 人 組 必 須 由 自 己 撰 寫 主 程 式 ; 團 體 組 可 由 團 隊 分 工 或 共 同 撰 寫 主 程 式 二 解 題 流 程 與 上 傳 規 則. 解 題 完 成 後, 需 送 出 單 獨 一 個 程 式 原 始 碼 的 檔 案 內 容 至 評 分 系 統 送 出 的 程 式 原 始 碼, 需 確 保 能 在 評 審 主 機 上 正 常 編 譯 / 執 行 但 題 目 另 有 規 定 者, 如 僅 需 上 傳 輸 出 檔 或 其 他 檔 案 者, 則 從 其 規 定. 送 出 的 程 式 原 始 碼 視 不 同 語 言 而 定, 可 能 需 先 經 過 編 譯 或 可 直 接 由 直 譯 器 執 行 需 先 經 過 編 譯 之 程 式, 若 編 譯 發 生 任 何 錯 誤 或 超 出 資 源 限 制, 則 評 分 系 統 得 顯 示 編 譯 錯 誤 之 原 因, 但 不 須 編 譯 之 程 式, 不 在 此 限. 程 式 應 在 開 始 執 行 後 不 經 任 何 手 動 操 作, 自 動 由 標 準 輸 入 (stdin) 讀 取 輸 入 資 料, 將 結 果 輸 出 至 標 準 輸 出 (stdout) 後 立 刻 結 束 程 式 標 準 輸 入 與 標 準 輸 出 之 操 作, 請 參 考 各 語 言 之 額 外 說 明. 輸 出 完 畢 後 程 式 應 立 刻 自 動 結 束, 以 免 未 關 閉 而 被 程 式 判 定 為 超 出 時 間 限 制 (TLE) 若 程 式 執 行 中 途 因 發 生 錯 誤 而 跳 出 錯 誤 視 窗 或 異 常 情 形, 仍 可 能 被 判 定 為 超 出 時 間 限 制 (TLE) 輸 出 答 案 錯 誤 (WA) 或 執 行 時 期 錯 誤 (RE), 由 系 統 實 際 判 定 為 準 5. 各 題 均 依 題 目 需 要, 訂 有 固 定 之 輸 入 與 輸 出 格 式 對 於 每 組 測 試 資 料, 評 審 均 會 使 用 除 範 例 以 外 之 至 少 一 組 測 試 資 料 測 試, 故 錯 誤 之 程 式 可 能 雖 能 通 過 範 例 測 試 資 料 或 其 餘 資 料, 但 仍 無 法 得 分 6. 若 程 式 在 規 定 之 執 行 時 間 記 憶 體 使 用 量 系 統 資 源 使 用 限 制 下, 正 確 輸 出 題 目 所 要 求 之 結 果, 則 該 次 測 試 視 為 通 過, 否 則 視 為 不 通 過 但 另 有 規 定 者, 從 其 規 定 7. 原 始 碼 檔 案 大 小 限 制 編 譯 時 間 與 記 憶 體 空 間 限 制 以 評 分 系 統 之 設 定 為 準 8. 若 有 相 同 程 式 碼 前 後 評 測 結 果 不 一 致 的 情 形, 請 即 通 知 競 賽 單 位 進 行 系 統 調 整 9. 解 題 活 動 中 不 得 進 行 任 何 非 基 於 正 當 目 的 操 作 系 統 之 行 為
0. 解 題 期 間 內, 考 生 可 以 由 系 統 進 行 多 次 傳 送 但 出 於 系 統 穩 定 性 與 負 載 考 量, 得 另 行 限 制 最 大 傳 送 次 數 與 最 小 傳 送 間 隔. 請 勿 使 用 系 統 相 關 指 令, 如 C 語 言 中 system( PAUSE ) 或 類 似 函 數, 或 是 進 行 system call 呼 叫 等 任 何 非 運 算 功 能, 以 免 被 判 定 為 使 用 被 限 制 的 函 數 (RF) 執 行 時 期 錯 誤 (RE) 或 輸 出 答 案 錯 誤 (WA). 參 賽 者 不 得 試 圖 存 取 作 業 系 統 之 控 制 功 能 或 越 權 操 作. 參 賽 者 不 得 試 圖 竄 改 評 分 系 統 或 損 害 其 功 能. 送 出 的 程 式 不 得 存 取 系 統 登 錄 網 路 外 接 設 備 或 檔 案 系 統 三 題 目 描 述 細 則. 若 寫 作 X,Y K 或 X,Y 均 介 於 與 K 之 間, 則 表 示 同 時 滿 足 X K 且 Y K, 而 X 與 Y 之 間 在 此 沒 有 規 定 特 定 的 大 小 關 係. 以 空 白 分 隔 者, 指 同 一 列 的 兩 相 鄰 項 目 之 間 以 恰 一 個 空 白 分 隔. 輸 入 與 輸 出 的 每 列 均 應 以 換 列 符 號 \n (ASCII 0) 結 束, 並 請 勿 輸 出 多 餘 空 白 多 餘 換 列 或 符 號, 如 "please enter an integer" 等 非 題 目 規 定 的 輸 出 若 正 確 答 案 為 Yes, 但 你 的 輸 出 為 YES 或 Y, 則 系 統 將 會 因 答 案 錯 誤 而 評 定 為 錯 誤 ; 若 答 案 為 " " ( 中 間 有 空 格 ), 但 你 的 輸 出 為 "" ( 中 間 沒 有 空 格 ) " " 或 " " ( 前 面 或 後 面 輸 出 多 餘 空 白 ), 系 統 也 可 能 評 為 錯 誤, 反 之 亦 然. 以 空 白 分 隔 者, 指 同 一 列 的 兩 相 鄰 項 目 之 間 以 恰 一 個 空 白 分 隔 5. 當 題 目 要 求 輸 出 兩 列, 每 列 各 一 個 數 值 時, 設 應 輸 出 之 答 案 依 序 是 與, 若 以 @ 表 示 換 列 符 號 (\n), 則 應 輸 出 @@, 而 非 @ ( 最 後 沒 換 列 ) @@ ( 有 多 餘 換 列 ) @@ @@@ 或 @@@ 等 6. 輸 入 與 輸 出 的 正 整 數 數 値 應 使 用 連 續 的 十 進 位 阿 拉 伯 數 字 表 示, 以 數 字 至 9 開 頭 ; 負 整 數 數 値 以 - 連 接 其 絕 對 值 ( 正 整 數 ) 表 示, 零 以 單 一 個 阿 拉 伯 數 字 0 表 示 浮 點 數 以 "X.Y" 的 形 式 表 示, 其 中 X 與 Y 均 為 十 進 位 整 數, 且 X 若 不 為 零, 則 不 以 0 開 頭 7. 每 題 有 一 或 多 組 測 試 資 料, 每 組 測 試 資 料 獨 立 評 分, 其 中 可 能 包 含 一 或 多 次 測 試, 若 所 有 測 試 均 通 過, 則 該 組 測 試 資 料 計 為 滿 分 ; 測 試 有 任 一 部 份 錯 誤 者, 視 為 全 部 錯 誤, 無 法 得 分 但 題 目 另 有 部 分 給 分 規 則 或 其 他 規 定 者, 從 其 規 定 8. 本 平 台 所 提 供 之 各 語 言 均 提 供 官 方 執 行 環 境, 請 確 認 該 環 境 正 常 運 作, 且 說 明 所 附 之 自 動 測 試 程 式 可 以 正 常 評 分 所 有 答 題 所 需 之 程 式 碼 均 需 撰 寫 於 該 官 方 執 行 環 境 所 規 定 之 同 一 個 檔 案 中, 並 請 勿 修 改 額 外 設 定 值, 以 免 造 成 評 審 主 機 無 法 正 常 評 分 而 無 法 得 分 9. 答 題 時 應 注 意 數 值 範 圍, 對 於 範 圍 較 大 之 整 數 使 用 C# 語 言 中 的 long long; VB 語 言 中 的 Long Decimal 或 Currency 等 範 圍 較 大 的 型 態, 或 自 行 使 用 陣 列 處 理 數 值 運 算 與 儲 存, 以 避 免 溢 位 而 導 致 答 案 錯 誤 使 用 浮 點 數 者, 須 自 行 承 擔 因 此 造 成 計 算 誤 差 而 答 案 錯 誤 之 風 險 0. 本 平 台 提 供 多 種 程 式 語 言 作 答 然 而 使 用 不 同 的 語 言 撰 寫 程 式, 可 能 會 有 許 多 內 建 函 數 功 能 記 憶 體 使 用 量 以 及 執 行 效 能 上 差 異, 並 可 能 因 此 導 致 個 別 語 言 有 特 定 優 勢 為 了 盡 力 消 除 語 言 之 間 的 差 異, 以 維 持 比 賽 之 公 平 性, 題 目 設 計 時 將 會 盡 力 確 保 對 於 所 開 放 使 用 之 各 種 語 言 而 言, 均 存 在 至 少 一 種 能 獲 得 滿 分 的 解 答 程 式 但 可 能 因 特 定 語 言 導 致 之 解 答 難 易 度 差 異, 此 時 主 辦 單 位 將 酌 量 放 寬 時 間 或 不 予 處 理. 各 題 目 之 執 行 時 間 限 制 記 憶 體 空 間 限 制 原 始 碼 檔 案 大 小 限 制 與 其 他 資 源 限 制, 以 評 測 系 統 所 公 布 之 設 定 為 主. 執 行 主 機 環 境 :Windows Server 0, 6-bit, Intel Xeon CPU E-0v. 若 題 目 內 容 有 疑 義, 以 電 子 郵 件 方 式 或 系 統 詢 問 功 能 進 行 詢 問. 若 題 目 有 任 何 補 充 說 明 或 修 正, 將 於 題 目 頁 公 告
題 組 一 : 徽 章 題 組 敘 述 : 某 島 國 其 國 號 亦 不 詳, 其 領 土 範 圍 亦 不 詳 其 某 知 名 政 黨, 有 眾 多 的 附 屬 團 體 儲 存 黨 產 每 個 團 體 有 唯 一 的 編 號, 在 此 題 組 中, 團 體 編 號 均 以 a-b-c-d-e-f-g-h 的 格 式 表 示, 其 中 a, b, c, d, e, f, g, h 均 為 十 進 位 表 示 之 正 整 數 為 了 保 護 這 些 團 體 之 間 的 秘 密 通 信 的 隱 密 性, 這 些 團 體 的 所 有 書 面 文 件 都 只 會 附 上 其 徽 章 圖 示, 而 不 會 寫 上 實 際 的 編 號 每 個 團 體 的 徽 章 圖 示 是 基 於 該 團 體 編 號 所 產 生 的, 我 們 可 以 在 方 格 圖 上 繪 製 此 徽 章, 方 格 圖 即 將 紙 張 由 左 而 右 由 上 而 下 切 割 成 任 意 等 份, 類 似 圍 棋 棋 盤 的 長 相, 再 依 序 以 二 維 座 標 表 示 其 方 格 編 號, 每 格 可 能 為 黑 色 或 是 白 色, 也 即 以 黑 白 兩 色 表 示 此 點 陣 圖 形 假 設 此 方 格 圖 往 上 下 左 右 無 限 延 伸, 先 選 擇 其 中 一 格 做 為 中 心 方 格 接 著, 對 於 所 有 相 鄰 的 上 下 兩 方 格 而 言, 若 上 方 之 方 格 編 號 為 (x, y), 則 下 方 之 方 格 編 號 為 (x +, y), 反 之 亦 可 推 得 ; 對 於 相 鄰 的 左 右 兩 方 格 而 言, 若 左 方 之 方 格 編 號 為 (x, y), 則 右 方 之 方 格 編 號 為 (x, y + ), 反 之 亦 可 推 得 位 於 某 方 格 之 上 方 之 左 方 的 方 格, 稱 為 該 方 格 之 左 上 方 方 格, 以 此 類 推 若 某 格 之 方 格 編 號 為 (x, y), 則 我 們 稱 該 方 格 之 垂 直 位 置 為 x 水 平 位 置 為 y 對 於 編 號 為 a-b-c-d-e-f-g-h 的 團 體, 其 徽 章 圖 形 依 下 列 規 則 繪 製. 除 中 心 方 格 先 填 為 黑 色 外, 其 餘 方 格 均 先 填 為 白 色. 從 中 心 方 格 出 發, 不 計 此 格, 往 正 上 方 數 連 續 a 格 均 填 為 黑 色. 從 中 心 方 格 出 發, 不 計 此 格, 往 右 上 方 數 連 續 b 格 均 填 為 黑 色. 從 中 心 方 格 出 發, 不 計 此 格, 往 正 右 方 數 連 續 c 格 均 填 為 黑 色 5. 從 中 心 方 格 出 發, 不 計 此 格, 往 右 下 方 數 連 續 d 格 均 填 為 黑 色 6. 從 中 心 方 格 出 發, 不 計 此 格, 往 正 下 方 數 連 續 e 格 均 填 為 黑 色 7. 從 中 心 方 格 出 發, 不 計 此 格, 往 左 下 方 數 連 續 f 格 均 填 為 黑 色 8. 從 中 心 方 格 出 發, 不 計 此 格, 往 正 左 方 數 連 續 g 格 均 填 為 黑 色 9. 從 中 心 方 格 出 發, 不 計 此 格, 往 左 上 方 數 連 續 h 格 均 填 為 黑 色 最 後, 找 出 足 以 涵 蓋 所 有 黑 色 方 格 之 最 小 長 方 形 區 域 ( 含 正 方 形 ), 切 割 出 來 即 形 成 該 團 體 之 徽 章 方 格 圖, 並 設 其 方 格 圖 形 由 上 至 下 共 有 NN 格 由 左 至 右 共 有 MM 格, 我 們 定 義 此 徽 章 之 長 度 為 NN 寬 度 為 MM 並 且 將 最 上 面 的 黑 色 方 格 座 標 之 垂 直 位 置 設 為, 最 左 邊 的 黑 色 方 格 座 標 之 水 平 位 置 設 為 依 據 此 規 則, 對 於 任 何 一 個 團 體 編 號, 即 可 得 到 其 唯 一 的 徽 章 圖 示 以 及 各 黑 色 方 格 的 編 號 舉 例 而 言, 對 於 團 體 編 號 為 ------- 的 徽 章, 唯 一 對 應 的 徽 章 圖 示 與 各 黑 色 格 子 的 編 號 如 下 所 示, 並 稱 此 徽 章 方 格 圖 之 長 度 為 9 寬 度 為 9, 而 中 心 方 格 的 編 號 為 (5,5): (, ) (, ) (, ) (, 7) (, ) (, 5) (, 6) (5, ) (5, ) (5, ) (5, 5) (5, 6) (5, 7) (5, 8) (6, ) (6, 5) (6, 6) (7, ) (7, 5) (7, 7) (8, 8) (9, 9) 請 依 據 這 些 規 則 回 答 下 列 問 題
題 組 一 第 一 題 : 徽 章 之 黑 色 方 格 數 如 題 組 敘 述 所 示, 給 定 團 體 編 號 a-b-c-d-e-f-g-h 後, 則 可 以 繪 製 其 徽 章 方 格 圖 其 圖 形 的 每 格 黑 色 方 格 都 需 要 使 用 恰 好 一 單 位 的 黑 色 顏 料, 而 其 餘 的 方 格 則 不 須 顏 料 請 問 至 少 需 要 多 少 單 位 的 黑 色 顏 料, 才 能 繪 製 成 徽 章 方 格 圖 呢? 測 試 資 料 的 輸 入 共 有 8 列, 每 列 均 為 一 個 正 整 數, 依 序 為 題 組 敘 述 中 之 正 整 數 a, b, c, d, e, f, g, h 請 輸 出 一 列, 其 中 包 含 一 個 正 整 數, 表 示 至 少 需 要 多 少 單 位 的 黑 色 顏 料 9 範 例 說 明 一 : 範 例 說 明 二 : 5 範 例 說 明 三 : 試 資 料 配 分, 否 則 給 部 分 分 數 或 不 給 分, 滿 分 0 分 所 有 輸 入 數 值 均 不 超 過 0 [ 分 ] 所 有 輸 入 數 值 均 不 超 過 000 [ 分 ] 所 有 輸 入 數 值 均 不 超 過 00000 [ 分 ] 所 有 輸 入 數 值 均 不 超 過 0000000 [ 分 ] 所 有 輸 入 數 值 均 不 超 過 000000000 [ 分 ]
題 組 一 第 二 題 : 徽 章 之 區 域 大 小 如 題 組 敘 述 所 示, 給 定 團 體 編 號 a-b-c-d-e-f-g-h 後, 則 可 以 計 算 其 徽 章 方 格 圖 之 長 度 與 寬 度 ( 其 定 義 如 題 組 敘 述 所 示 ) 請 幫 忙 計 算 其 值 測 試 資 料 的 輸 入 共 有 8 列, 每 列 均 為 一 個 正 整 數, 依 序 為 題 組 敘 述 中 之 正 整 數 a, b, c, d, e, f, g, h 請 輸 出 兩 列, 每 列 均 為 一 個 正 整 數, 第 一 列 為 繪 製 完 成 後 之 徽 章 長 度 NN, 第 二 列 為 繪 製 完 成 後 之 徽 章 寬 度 MM 範 例 說 明 一 : 9 9 範 例 說 明 二 : 5 7 範 例 說 明 三 : 試 資 料 配 分, 否 則 給 部 分 分 數 或 不 給 分, 滿 分 0 分 正 確 答 案 NN, MM 0 [5 分 ] 正 確 答 案 NN, MM 000 [5 分 ] 正 確 答 案 NN, MM 000000 [5 分 ] 正 確 答 案 NN, MM 000000000 [5 分 ]
題 組 一 第 三 題 : 徽 章 之 團 體 編 號 如 題 組 敘 述 所 示, 若 已 知 徽 章 方 格 圖, 即 可 推 得 唯 一 的 團 體 編 號 a-b-c-d-e-f-g-h, 請 依 據 題 組 敘 述 中 之 定 義, 幫 忙 計 算 原 始 的 團 體 編 號 是 多 少 呢? 測 試 資 料 的 輸 入 共 有 兩 列, 每 列 包 含 一 個 正 整 數 第 一 列 為 繪 製 完 成 後 之 徽 章 長 度 NN, 第 二 列 為 繪 製 完 成 後 之 徽 章 寬 度 MM (NN, MM ) 接 著 共 有 NN 列, 每 列 共 有 MM 個 字 元, 每 個 字 元 只 可 能 為 0 或, 其 中 字 元 0 表 示 該 方 格 為 白 色, 字 元 表 示 該 方 格 為 黑 色 其 徽 章 方 格 圖 均 為 合 法 請 輸 出 八 列, 每 列 均 為 一 個 正 整 數, 依 序 為 原 始 的 團 體 編 號 依 照 題 組 敘 述 中 的 表 示 法 a-b-c-d-e-f-g-h 中, 對 應 之 正 整 數 a, b, c, d, e, f, g, h 9 9 00000000 00000000 0000000 000000 00 000000 000000 00000000 00000000 7 00 00 00 00 5 試 資 料 配 分, 否 則 給 部 分 分 數 或 不 給 分, 滿 分 0 分 輸 入 資 料 NN, MM 0 [5 分 ] 輸 入 資 料 NN, MM 00 [5 分 ] 輸 入 資 料 NN = MM 000 [5 分 ] 輸 入 資 料 NN, MM 000 [5 分 ]
題 組 一 第 四 題 : 徽 章 計 數 如 題 組 敘 述 所 示, 若 已 知 繪 製 完 成 後 的 徽 章 方 格 圖 之 長 度 為 NN 以 及 寬 度 為 MM( 其 定 義 如 題 組 敘 述 所 示 ), 請 問 共 有 幾 種 可 能 的 團 體 編 號 呢? 以 格 式 a-b-c-d-e-f-g-h 表 示 其 團 體 編 號, 若 兩 個 團 體 編 號 中 對 應 之 a, b, c, d, e, f, g, h 其 中 任 一 數 不 相 同, 就 視 為 不 同 的 團 體 編 號 第 一 列 有 正 整 數 TT, 滿 足 TT 00 接 著 共 有 TT 組 輸 入 每 組 測 試 資 料 的 輸 入 為 一 列, 包 含 兩 個 正 整 數, 以 一 個 空 白 分 隔, 依 序 為 繪 製 完 成 後 之 徽 章 長 度 NN 寬 度 MM, 且 NN, MM 對 於 共 有 幾 種 可 能 的 團 體 編 號 之 值, 請 輸 出 該 值 除 以 質 數 000000007 所 得 之 餘 數 5 5 範 例 輸 入 四 : 7 95 87 範 例 輸 入 五 : 7686 7896 000000000 000000000 0 範 例 輸 出 四 : 889 77580 範 例 輸 出 五 : 65068 865 範 例 說 明 二 : 兩 組 合 法 的 團 體 編 號 分 別 為 :------- 與 ------- 範 例 說 明 四 : 其 中 第 一 組 輸 入 共 有 8898 組 合 法 的 團 體 編 號, 此 值 除 以 000000007 所 得 之 餘 數 為 889 第 二 組 輸 入 共 有 79699878 組 合 法 的 團 體 編 號, 此 值 除 以 000000007 所 得 之 餘 數 為 77580 範 例 說 明 五 : 其 中 第 二 組 輸 入 共 有 8609555787809676095790768876898960000000 組 合 法 的 團 體 編 號, 此 值 除 以 000000007 所 得 之 餘 數 為 865 試 資 料 配 分, 否 則 給 部 分 分 數 或 不 給 分, 滿 分 70 分 輸 入 NN, MM [5 分 ] ( 提 示 : 可 以 先 在 本 機 計 算 答 案 後 存 於 表 格 輸 出 ) 輸 入 NN, MM 0 [5 分 ] 輸 入 NN, MM 00 [5 分 ] 輸 入 NN, MM 000 [5 分 ] 輸 入 NN, MM 00000 [5 分 ] 輸 入 NN, MM 000000000 [5 分 ] 輸 入 NN = MM 00 且 均 為 偶 數 [5 分 ] 輸 入 NN = MM 00 且 均 為 奇 數 [5 分 ] 輸 入 NN = MM 00 [5 分 ] 輸 入 NN = MM 000 且 均 為 偶 數 [5 分 ] 輸 入 NN = MM 000 且 均 為 奇 數 [5 分 ] 輸 入 NN = MM 000 [5 分 ] 輸 入 NN = MM 00000 [5 分 ] 輸 入 NN = MM 000000000 [5 分 ]
題 組 一 第 五 題 : 徽 章 之 修 復 工 作 如 題 組 敘 述 所 示, 若 已 知 徽 章 方 格 圖, 即 可 推 得 唯 一 的 團 體 編 號 年 代 久 遠, 白 色 恐 怖 猖 獗, 你 所 拿 到 的 徽 章 方 格 圖 已 經 有 若 干 破 損, 無 法 辨 識 其 格 子 是 何 種 顏 色 在 得 知 徽 章 方 格 圖 之 長 度 與 寬 度 ( 如 題 組 敘 述 中 定 義 ) 之 後, 你 已 經 能 成 功 地 確 定 某 些 編 號 的 格 子 一 定 是 黑 色, 而 其 餘 的 格 子 並 無 法 確 定 其 顏 色 請 問 在 以 上 條 件 之 下, 對 於 所 有 可 能 造 成 此 結 果 之 團 體 編 號, 以 格 式 a-b-c-d-e-f-g-h 表 示, 則 (a + b + c + d + e + f + g + h) 之 最 小 值 為 何 呢? 如 果 修 復 失 敗, 可 能 會 導 致 無 解, 此 時 請 以 0 表 示 此 最 小 值 測 試 資 料 的 輸 入 第 一 列 為 正 整 數 NN, MM, KK, 以 一 個 空 格 分 隔, 其 中 NN 為 繪 製 完 成 後 之 徽 章 長 度,MM 為 繪 製 完 成 後 之 徽 章 寬 度,KK 為 已 經 確 定 為 黑 色 的 方 格 數 (NN, MM ) 接 著 共 有 KK 列, 其 中 第 ii 列 的 格 式 為 正 整 數 XX ii, YY ii, 表 示 編 號 為 (XX ii, YY ii ) 的 方 格 確 定 為 黑 色 請 輸 出 一 列, 其 中 包 含 一 個 正 整 數, 表 示 題 目 敘 述 中 所 述 (a + b + c + d + e + f + g + h) 之 最 小 值 如 果 不 存 在 任 何 可 能 的 團 體 編 號, 則 該 列 請 輸 出 0 即 可 8 範 例 輸 入 四 : 5 5 8 5 5 8 8 0 範 例 輸 出 四 : 範 例 說 明 一 二 : 唯 一 可 能 的 團 體 編 號 為 :-------, 其 中 (a + b + c + d + e + f + g + h) 之 值 為 8 範 例 說 明 四 : 可 能 的 團 體 編 號 如 ------- 或 ------- 等, 前 者 之 其 值 較 小 試 資 料 配 分, 否 則 給 部 分 分 數 或 不 給 分, 滿 分 60 分 輸 入 NN, MM, KK 0 [0 分 ] 輸 入 NN, MM, KK 50 [0 分 ] 輸 入 NN, MM, KK 00 [0 分 ] 輸 入 NN, MM, KK 500 [0 分 ] 輸 入 NN, MM, KK 5000 [0 分 ] 輸 入 NN, MM, KK 00000 [0 分 ]
題 組 一 第 六 題 : 徽 章 探 測 如 題 組 敘 述 所 示, 若 已 知 徽 章 方 格 圖, 即 可 推 得 唯 一 的 團 體 編 號 在 那 不 知 為 何 的 年 代, 你 隨 風 標 盪 著, 剎 那 間 瞥 見 了 張 徽 章 方 格 圖, 然 而, 團 體 編 號 依 然 模 糊 不 清 假 設 這 張 徽 章 方 格 圖 當 初 是 依 據 合 法 的 團 體 編 號 所 繪 製 而 成, 但 歷 經 歲 月 滄 桑, 徽 章 方 格 圖 中 已 經 有 若 干 ( 可 能 沒 有, 也 可 能 多 個 ) 白 色 格 子 被 汙 染 為 黑 色, 但 若 繪 製 後 該 格 為 黑 色 格 子, 則 必 然 會 維 持 黑 色 給 定 此 被 汙 染 後 的 徽 章 方 格 圖, 請 問 在 已 知 徽 章 方 格 圖 正 確 長 度 與 寬 度 ( 其 定 義 如 題 組 敘 述 所 示 ) 的 情 況 下, 對 於 所 有 可 能 的 團 體 編 號, 以 格 式 a-b-c-d-e-f-g-h 表 示, 則 (a + b + c + d + e + f + g + h) 之 最 大 值 為 何 呢? 如 果 探 測 過 程 中 發 生 錯 誤, 可 能 會 導 致 無 解, 此 時 請 以 0 表 示 此 最 大 值 測 試 資 料 的 輸 入 共 有 兩 列, 每 列 包 含 一 個 正 整 數 第 一 列 為 繪 製 完 成 後 之 徽 章 長 度 NN, 第 二 列 為 繪 製 完 成 後 之 徽 章 寬 度 MM (NN, MM ) 接 著 共 有 NN 列, 每 列 共 有 MM 個 字 元, 表 示 被 汙 染 後 的 徽 章 方 格 圖, 每 個 字 元 只 可 能 為 0 或, 其 中 字 元 0 表 示 該 方 格 為 白 色, 字 元 表 示 該 方 格 為 黑 色 請 輸 出 一 列, 其 中 包 含 一 個 正 整 數, 表 示 題 目 敘 述 中 所 述 (a + b + c + d + e + f + g + h) 之 最 大 值 如 果 不 存 在 任 何 可 能 的 團 體 編 號, 則 該 列 請 輸 出 0 即 可 8 9 9 00000000 00000000 0000000 000000 00 000000 000000 00000000 000 7 00 範 例 說 明 三 : 若 團 體 編 號 為 5------- 且 標 示 之 位 置 為 中 心 方 格 時, 此 時 (a + b + c + d + e + f + g + h) = 為 最 大 值, 此 時 以 標 示 之 位 置 為 受 汙 染 的 方 格 00 試 資 料 配 分, 否 則 給 部 分 分 數 或 不 給 分, 滿 分 50 分 輸 入 NN, MM 0 [0 分 ] 輸 入 NN, MM 0 [0 分 ] 輸 入 NN, MM 50 [0 分 ] 輸 入 NN, MM 00 [0 分 ] 輸 入 NN, MM 000 [0 分 ]