航空拍照圖 (APCS 2025-10 中級)

1.0s 256M

某地區在不同時間由飛機拍攝了兩張灰階空拍照片。每張照片可表示為一個 \(R\) 列、\(C\) 欄的二維陣列;每個元素是該位置的灰階值。

為了比較兩張照片,你可以分別將每張照片順時針旋轉 \(0^\circ\)、\(90^\circ\)、\(180^\circ\) 或 \(270^\circ\)。

若旋轉後兩張照片的列數或欄數不同,這組旋轉方式的相似度為 \(0\%\)。 否則,設兩張照片在相同位置具有相同灰階值的格子數為 \(S\),則相似度為

\[\left\lfloor \frac{100S}{RC} \right\rfloor\%.\]

請求出所有旋轉方式中最高的相似度。

輸入格式

第一列包含兩個整數 \(R\)、\(C\),表示每張照片的列數與欄數。

接下來 \(R\) 列,每列包含 \(C\) 個整數,表示照片 A。

再接下來 \(R\) 列,每列包含 \(C\) 個整數,表示照片 B。

限制

  • \(1\le R,C\le200\)
  • \(0\le A_{i,j},B_{i,j}\le255\)

輸出格式

輸出最高相似度的整數值,並在後方接上一個百分比符號 %。

評分說明

每一筆測試資料的執行時間限制均為 \(1\) 秒,依正確通過的測試資料筆數給分。其中:

子題組 分數 額外限制
1 60 \(R=1\)
2 40 無額外限制

範例輸入

6 5
0 1 1 1 1
0 2 2 2 2
0 3 3 3 3
0 4 4 4 4
0 5 5 5 5
0 6 6 6 6
6 6 6 6 6
5 5 5 5 5
4 4 4 4 4
7 7 7 7 0
8 8 8 8 0
9 9 9 9 0

範例輸出

50%

範例解釋

將照片 B 旋轉 \(180^\circ\) 後,共有 \(15\) 個位置與照片 A 的灰階值相同。 照片共有 \(6\times5=30\) 個位置,因此相似度為 \(\left\lfloor100\times15/30\right\rfloor=50\%\),且其他旋轉方式 不會得到更高的相似度。

題目來源

APCS 2025 年 10 月中級實作題第 2 題。

題敘參考 ZeroJudge r489「航空拍照圖」 整理,細節可能與正式試題有出入。

題目頁說明

快速鍵

主要功能

  • 範例測試 — 執行題目附帶的範例測資並自動比對預期輸出。
  • 自訂測試 — 自己貼 stdin 執行程式。可勾選「與預期輸出比對 (diff)」做行對行比對。
  • 模板 — 貼上你在個人資料設定的預設程式碼模板。
  • 協作 — 與其他同學共筆編輯這題的程式碼。
  • 自動草稿 — 編輯器內容每 1.5 秒自動存到瀏覽器(per 帳號 / 題目 / 語言)。
  • 提交 — 把程式碼交給 judge 評測,回傳 AC / WA / TLE 等結果。

限制

  • 程式碼最多 65,536 字元
  • 自訂測試 stdin 與預期輸出各最多 1 MB (約 100 萬字元)
  • 自訂測試每人約 3 秒 1 次 (範例測試 1 秒 1 次)
  • 自訂測試有 15 秒 牆鐘上限;範例測試和正式評測一樣,照題目的時間限制
  • 互動題不提供自訂測試(無法模擬與 judge 互動)。
  • 提交評測本身沒有 rate limit,但同題短時間內多次提交會被視為刷分。