a227. G. 看星星的鄭教授

內容

2022 網際網路程式設計全國大賽國中組決賽

「だって僕は星だから・Stellar Stellar！」、「星星點燈，照亮我的家門」、「馬鹿なわたしは歌うだけ・ぶちまけちゃおうか、星に」

從古至今有許多歌曲都在詠嘆天上繁星的浪漫。

不管是和朋友一起看星星，或是和喜歡的另一半一起看星星，知道哪個星星是哪個星座都會給你加不少的分。

為了簡化問題，我們假設星空是二維平面上一個 N × M 的長方形棋盤方格，N,M 分別稱為星空的南北高度以及東西寬度。

在這個棋盤方格的 N × M 格當中，每一格裡面最多只會有一顆星星。
我們將由這個棋盤方格由左至右、由上到下編號為 (x,y)，其中 1 ≤ x ≤ M,1 ≤ y ≤ N。若在某一格 (x,y) 當中有一顆星星，則稱該星星的座標是 (x,y)。x 和 y 分別被稱為該星星的 x 座標與 y 座標。x 由左而右遞增，y 由上至下遞增。注意 y 座標遞增的方向。
一些星星會組成一個星座，並且所有星星都恰好屬於一個星座。星座以英文小寫和大寫字母作為編號。你不應該對此題中的星座形狀有任何多餘的假設。
在晚上的時候，我們能看到的所有星星是 x 座標介在 L,R（包含）之間的星星。如果一個星座的所有星星都看得到的話，我們稱這個星座是能被完整看到的。
因為地球的公轉，每一天晚上看得到的星星集合都不一樣，因此能看到的星座也不一定。每過了一天，所有星星都會向棋盤方格的右邊移動一格。也就是說，每過一天，原本座標是 (x,y) 的星星會移動到 (x + 1,y) 去。特別地，原本 x 座標是 M 的那些星星，若他們原本座標為 (M,y)，過了一天之後則會移動到 (1,y) 去。

接下來鄭教授有 Q 個問題，想請問你在一年的第 x_i天當中，能完整看到編號 c_i的星座嗎？請注意，如果整個棋盤方格上沒有一個星星是 c_i屬於這個星座，那麼請你當作看不到這個星座而輸出No。

輸入說明

輸入的第一行有三個正整數 N,M,Q，分別表示星空的南北高度，星空的東西寬度，以及詢問的個數。輸入的第二行有兩個整數 L,R，代表在晚上的時候只能看到 x 座標處於 L,R 的星星。

接下來 N 行，每行都有一個長度為 M 的字串 b_i，其中 b_i的第 j 個字元 b_i,j代表在一年的第一天當中，座標 (j,i) 的星星是屬於哪一個星座。如果 b_i,j= .代表在一年的第一天當中，沒有星星處在座標 (j,i)。

接下來 Q 行，每行都有一個正整數 x_i以及一個字元 c_i，中間以空白隔開，代表鄭教授想請問你在一年的第 x_i天當中，能完整看到編號 c_i的星座嗎？

1 ≤ N ≤ 100
1 ≤ M ≤ 10⁵
1 ≤ Q ≤ 100000
1 ≤ L ≤ R ≤ M
b_i,j只會是「.」，小寫英文字母或是大寫英文字母
1 ≤ x_i≤ M
c_i只會是小寫英文字母或是大寫英文字母，即a到z和A到Z

輸出說明

請輸出 Q 行，第 i 行輸出Yes或No代表第 i 個詢問是否可以完整看得到星座 c_i。

範例輸入

10 25 10
5 20
.................O..O.... .CCCC.................SS. .....................S... ....Z.....Z...........S.. .......Z..Z............S. .............X....X..SS.. .DD..F................... .D.D.FFFFFF.....X........ .D.D.F........X...X...... .DD..F...........OO...N..
4 O
15 Z
25 O
4 X
4 N
20 Z
1 Z
5 Z
25 S
16 N

範例輸出

No
No
Yes
No
No
No
Yes
Yes
No
Yes

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (2%): 1.0s , <1K
公開測資點#1 (2%): 1.0s , <1K
公開測資點#2 (2%): 1.0s , <50M
公開測資點#3 (2%): 1.0s , <1M
公開測資點#4 (2%): 1.0s , <1M
公開測資點#5 (2%): 1.0s , <1M
公開測資點#6 (2%): 1.0s , <1M
公開測資點#7 (2%): 1.0s , <1M
公開測資點#8 (2%): 1.0s , <1M
公開測資點#9 (2%): 1.0s , <1M
公開測資點#10 (2%): 1.0s , <1M
公開測資點#11 (2%): 1.0s , <10M
公開測資點#12 (2%): 1.0s , <10M
公開測資點#13 (2%): 1.0s , <10M
公開測資點#14 (2%): 1.0s , <10M
公開測資點#15 (2%): 1.0s , <10M
公開測資點#16 (2%): 1.0s , <10M
公開測資點#17 (2%): 1.0s , <10M
公開測資點#18 (2%): 1.0s , <50M
公開測資點#19 (2%): 1.0s , <10M
公開測資點#20 (2%): 1.0s , <10M
公開測資點#21 (2%): 1.0s , <10M
公開測資點#22 (2%): 1.0s , <10M
公開測資點#23 (3%): 1.0s , <10M
公開測資點#24 (3%): 1.0s , <10M
公開測資點#25 (3%): 1.0s , <10M
公開測資點#26 (3%): 1.0s , <10M
公開測資點#27 (3%): 1.0s , <10M
公開測資點#28 (3%): 1.0s , <10M
公開測資點#29 (3%): 1.0s , <50M
公開測資點#30 (3%): 1.0s , <50M
公開測資點#31 (3%): 1.0s , <50M
公開測資點#32 (3%): 1.0s , <50M
公開測資點#33 (3%): 1.0s , <50M
公開測資點#34 (3%): 1.0s , <50M
公開測資點#35 (3%): 1.0s , <50M
公開測資點#36 (3%): 1.0s , <50M
公開測資點#37 (3%): 1.0s , <50M
公開測資點#38 (3%): 1.0s , <50M
公開測資點#39 (3%): 1.0s , <50M
公開測資點#40 (3%): 1.0s , <50M

提示：

標籤:

2022國中組決賽

出處:

NPSC [管理者：

zero (管理員)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」