Tập Bắn

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie là một robot bò đứng ở vị trí $0$ trên trục số. Cô nhận được một chuỗi lệnh gồm $C$ ký tự và cần bắn trúng càng nhiều mục tiêu càng tốt. Có $T$ mục tiêu đặt tại các vị trí phân biệt trên trục số.

Các lệnh:

L: Di chuyển sang trái 1 đơn vị.
R: Di chuyển sang phải 1 đơn vị.
F: Bắn tại vị trí hiện tại (phá hủy mục tiêu nếu có; mỗi mục tiêu chỉ bị phá hủy một lần).

Bessie có thể thay đổi tối đa một lệnh trong chuỗi (thành L, R, hoặc F) trước khi thực hiện. Hãy tìm số mục tiêu tối đa Bessie có thể bắn trúng.

Dữ liệu vào

Dòng $1$ : Hai số nguyên $T$ và $C$ ( $1 \leq T, C \leq 10^{5}$ ).
Dòng $2$ : $T$ số nguyên phân biệt — vị trí các mục tiêu (trong khoảng $[- C, C]$ ).
Dòng $3$ : Xâu $C$ ký tự gồm các ký tự L, R, F.

Dữ liệu ra

In ra một số nguyên — số mục tiêu tối đa Bessie có thể bắn trúng sau khi thay đổi tối đa một lệnh.

Ràng buộc

Các test $4$ - $6$ : $T, C \leq 1000$ .
Các test $7$ - $15$ : Không có ràng buộc thêm.

Ví dụ

Input	Output	Giải thích
3 7 0 -1 1 LFFRFRR	3	Đổi lệnh cuối (R) thành F. Chuỗi mới: LFFRFRF. Bessie bắn tại vị trí -1, 0, 1 — trúng cả 3 mục tiêu.
1 5 0 FFFFF	1	Không cần thay đổi, lần bắn đầu tiên tại vị trí 0 đã trúng mục tiêu duy nhất.
5 6 1 2 3 4 5 FFRFRF	3	Tối đa bắn được 3 mục tiêu.

Bình luận

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