運貨站 (APCS 2022-10 中級)

運貨站有一個 \(R\) 列、\(C\) 行的長方形倉庫。列座標由上到下是 \(0\) 到 \(R-1\)，行座標由左到右是 \(0\) 到 \(C-1\)。一開始每一格都是 空的。

運貨站依序收到 \(n\) 件貨物。每件貨物由數個正方形方格組成，形狀分為 A、B、C、D、E 五種。下圖由左到右依序是 A、B、C、D、E；所有貨物的 方向固定，放入時不能旋轉或翻面。

若以 # 表示貨物佔用的方格、. 表示其外接矩形內沒有方格的位置， 五種形狀也可完整寫成：

A    B      C     D     E
#    ###    ##    ..#   .#
#           ##    ###   ##
#                       ##
#

第 \(i\) 件貨物的種類是 \(t_i\)，其頂端和倉庫頂端之間相隔 \(y_i\) 列， 因此貨物最上方的方格位於第 \(y_i\) 列。貨物的垂直位置在移動過程中 保持不變。

貨物會先從倉庫右側嘗試完全進入倉庫，再沿水平方向逐格向左推：

1. 先嘗試把整件貨物放在「剛好完全進入倉庫」的最右位置。
2. 如果這個位置超出倉庫或和已放入的貨物重疊，這件貨物無法進入， 會被丟棄。
3. 否則，只要再向左一格仍不會超出倉庫或碰到其他貨物，就繼續向左。
4. 當下一步無法移動時，貨物固定在目前位置。

貨物不能穿過其他貨物，也不能繞到障礙物左側的空洞。下圖示意一件 B 類貨物，最上方位於距離倉庫頂端兩列的位置，並由右向左推入。

如果一件貨物被丟棄，倉庫狀態不會改變。請依輸入順序處理所有貨物， 輸出最後倉庫內的空格數，以及被丟棄的貨物數。

輸入格式

第一行有三個整數 \(R\)、\(C\)、\(n\)，代表倉庫列數、行數與貨物數。

接下來 \(n\) 行，每行有一個大寫英文字母 \(t_i\) 與一個整數 \(y_i\)， 代表第 \(i\) 件貨物的種類與其最上方列座標。

限制

• \(1\le R\le30\)
• \(1\le C\le50\)
• \(1\le n\le200\)
• \(t_i\) 是 A、B、C、D、E 其中之一
• \(0\le y_i\)
• 保證貨物不會超出倉庫底部，也就是 \(y_i+\operatorname{height}(t_i)\le R\)

各形狀高度如下：

輸出格式

輸出一行兩個以空格分隔的整數，依序為：

剩餘空格數 被丟棄貨物數

評分說明

範例輸入 1

5 4 6
B 0
B 3
B 1
B 3
B 1
B 2

範例輸出 1

8 2

範例解釋 1

每件 B 類貨物都由三個水平相鄰方格組成。

1. B 0 放在第 0 列的第 0～2 行。
2. B 3 放在第 3 列的第 0～2 行。
3. B 1 放在第 1 列的第 0～2 行。
4. 第二件 B 3 需要再佔三格，但倉庫寬度只有 4，因此被丟棄。
5. 第二件 B 1 同樣被丟棄。
6. B 2 放在第 2 列的第 0～2 行。

最後的倉庫如下，# 是貨物、. 是空格：

###.
###.
###.
###.
....

共有 8 個空格、2 件貨物被丟棄。

範例輸入 2

5 6 6
C 1
A 1
E 0
E 0
B 0
A 0

範例輸出 2

13 2

範例解釋 2

下方動圖依序模擬六件貨物。碰撞符號表示貨物無法完整進入倉庫， 隨後被丟棄。

1. C 1 佔用第 1～2 列、第 0～1 行。
2. A 1 向左推到不能移動，佔用第 1～4 列的第 2 行。
3. 第一件 E 0 被下方既有貨物擋住，停止後佔用 \((0,4)\)、\((1,3)\)、\((1,4)\)、\((2,3)\)、\((2,4)\)。
4. 第二件 E 0 無法完全進入倉庫，因此被丟棄。
5. B 0 在入口位置會碰到 \((0,4)\)，無法穿到左側空洞，因此被丟棄。
6. A 0 可以放入第 0～3 列的第 5 行。

最後的倉庫如下：

....##
######
######
..#..#
..#...

共放入 \(4+4+5+4=17\) 格貨物，所以剩下 \(5\times6-17=13\) 格空間； 共有 2 件貨物被丟棄。

題目來源

APCS 2022 年 10 月實作題第 2 題； ZeroJudge j123「運貨站」； 王一哲題解。