trang chủ / đề bài / icpc21_mn_g

Bãi đỗ xe

Đề bài

Mô tả

Hôm nay thầy Tipu có buổi bảo vệ luận văn tại Trường Đại học Khoa học Tự nhiên TP.HCM, nên thầy lái ô tô đến trường. Bãi đỗ xe của trường là một dãy gồm n ô đỗ xe liên tiếp. Mỗi ô rộng một mét, vừa cho một xe máy. Một ô tô chiếm đúng hai ô kề nhau, tổng bề rộng hai mét. Ví dụ, bãi xe được mô tả bởi xâu XXXX..X.XXXX.X gồm 14 ô, trong đó các ô thứ 5, 6, 8, 13 còn trống.

Thầy Tipu muốn đỗ ô tô của mình trong bãi, nhưng một số ô đã có xe khác chiếm. Ngoài ra, đang có một hàng đợi gồm k xe xếp trước thầy để vào bãi. Mỗi xe trong hàng đợi khi vào bãi sẽ chiếm các ô trống bất kỳ: một ô cho xe máy và hai ô kề nhau cho ô tô. Trong trường hợp không còn chỗ, tất cả các xe đang ở trong hàng đợi sẽ rời khỏi trường và không chiếm ô nào.

Vì sắp đến giờ bảo vệ, thầy Tipu rất vội. May mắn là những người trong hàng đợi rất tốt bụng, họ đề nghị nhường thầy vào bãi trước. Thầy Tipu không muốn lợi dụng điều đó, nên thầy tự hỏi cần vượt qua bao nhiêu xe phía trước để vào bãi kịp giờ, biết rằng thầy chắc chắn sẽ trễ nếu trong bãi không còn chỗ nào vừa ô tô của thầy.

Lưu ý rằng những người trong hàng đợi có thể chọn chỗ đỗ cho xe của họ không khéo, khiến không còn chỗ cho ô tô của thầy Tipu.

Cho bãi xe gồm n ô, một số ô đã bị chiếm, và hàng đợi gồm k xe (có thể là xe máy hoặc ô tô) không tính ô tô của thầy Tipu. Với mỗi i từ 0 đến k, hãy xác định xem thầy Tipu có chắc chắn đỗ được ô tô hay không nếu thầy vào bãi ngay sau i xe đầu tiên của hàng đợi, bất kể các xe đó chọn ô nào.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên t: số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm hai dòng:
    • Dòng thứ nhất là một xâu gồm n ký tự, mỗi ký tự là '.' hoặc 'X'. Ký tự thứ i mô tả trạng thái của ô thứ i: '.' là ô trống, 'X' là ô đã bị chiếm.
    • Dòng thứ hai là một xâu gồm k ký tự, mỗi ký tự là 'M' hoặc 'C', lần lượt chỉ xe máy hoặc ô tô. Ký tự đầu tiên ứng với xe ở đầu hàng đợi, ký tự cuối cùng ứng với xe ở cuối hàng đợi.

Dữ liệu ra

In ra t dòng. Mỗi dòng gồm k+1 ký tự 'Y' hoặc 'N'. Với mỗi i từ 0 đến k, in 'Y' nếu thầy Tipu chắc chắn tìm được chỗ đỗ ô tô khi vào bãi ngay sau i xe đầu tiên của hàng đợi, bất kể các xe đó chiếm những ô nào; ngược lại in 'N'.

Ràng buộc

  • 1≤t≤50000.
  • 1≤n≤105, 1≤k≤n.
  • Tổng n của mọi bộ dữ liệu không vượt quá 106.

Ví dụ

Input Output Giải thích
1
XXXX..X.XXXX.X
MM
YNN Nếu vào đầu tiên, thầy Tipu đỗ được vào hai ô trống kề nhau. Ngược lại, xe máy đầu tiên có thể chiếm một trong hai ô đó và thầy không còn chỗ.
3
......
MMMC
.X..X.
MMM
......
CCCM
YYYNN
YNNN
YYNNN
Ở bộ thứ nhất, ba xe máy đầu tiên có thể đỗ thành M.M.M. và không còn hai ô trống kề nhau.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0