a329. TOI 2022/12 潛力組：螞蟻暗號

題目描述

有一條長 K+1 公分的紙帶，距離左邊界 1、2、…、K 公分處各寫一個字元。在其中 N 個不同的字元位置上各放一隻機器螞蟻，每隻起初面向左或右。

所有螞蟻同時以相同速率移動。兩隻螞蟻的位置重合時會立即各自掉頭，視為體積與轉向時間都可忽略。當已超出或抵達紙帶邊界的螞蟻數達到 M 隻以上時，所有螞蟻停止。此時從左到右列出仍有螞蟻停在上方的字元，即為訊息內容。請求出這個訊息。

輸入格式

第一行為整數 K 與長度 K 的字串，以空白分隔。5 ≤ K ≤ 2×10^6，字串僅包含大小寫英文字母與數字。

第二行為 N、M，1 ≤ M < N ≤ K。

接著 N 行，每行為整數 P_i、D_i，1 ≤ P_i ≤ K。P_i 為起始位置距離左邊界的公分數；D_i = 0 表示朝左，D_i = 1 表示朝右。所有 P_i 互不相同。

原題分組限制：10 分：N = 2。15 分：全部螞蟻起始朝向相同。35 分：N, K ≤ 500。40 分：無額外限制。

輸出格式

輸出一個字串，表示破解的訊息。保證訊息至少包含一個字元。

範例 1

輸入：

5 ACGKX
2 1
1 1
3 0

輸出：

K

範例 2

輸入：

5 ACGKX
3 1
1 0
2 1
3 0

輸出：

CG

範例 3

輸入：

16 helloMachineClub
2 1
7 1
12 0

輸出：

e

範例 4

輸入：

16 helloMachineClub
4 1
16 1
5 1
7 0
13 0

輸出：

Me

來源

TOI 2022 年 12 月歷屆題〈螞蟻暗號〉，依官方 PDF 重新整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202212/Ants.pdf

標籤：TOI 歷屆