Ninja và hẻm núi

Đ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

Dạng bài

Ngôn ngữ cho phép

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

Một ninja đang đứng dưới đáy một hẻm núi sâu, hẻm núi gồm hai vách đá song song thẳng đứng, mỗi vách cao $n$ mét. Mỗi vách được chia thành $n$ ô vuông cao $1$ mét và đánh số từ $1$ (dưới cùng) đến $n$ (trên cùng). Một số ô là an toàn (ninja có thể đứng trên đó), số khác là nguy hiểm (có gai, không thể đứng).

Ban đầu ninja đứng ở ô số $1$ của vách trái (ô này được đảm bảo là an toàn). Tại mỗi giây, ninja thực hiện đúng một trong ba hành động sau:

Leo lên ô liền trên (vị trí $x \to x + 1$ cùng vách).
Leo xuống ô liền dưới (vị trí $x \to x - 1$ cùng vách).
Nhảy sang vách đối diện và lên cao thêm $k$ ô (vị trí $x \to x + k$ , đổi vách).

Sau khi ninja đi xong, mực nước trong hẻm núi dâng lên $1$ mét (ban đầu mực nước ở mép dưới ô số $1$ ). Ninja không được đứng trên ô đã bị nước phủ: nói cách khác, sau khi ninja thực hiện hành động thứ $t$ thì các ô có số nhỏ hơn hoặc bằng $t$ đã bị ngập, ninja phải ở trên một ô có số lớn hơn $t$ .

Nếu ninja di chuyển tới một ô có số lớn hơn $n$ thì coi như đã thoát khỏi hẻm núi.

Hỏi ninja có thể thoát ra hay không?

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $k$ ( $1 \leq n, k \leq 10^{5}$ ) — chiều cao của hẻm núi và độ cao mỗi cú nhảy.
Dòng thứ hai là một xâu độ dài $n$ mô tả vách trái: ký tự thứ $i$ là X nếu ô thứ $i$ nguy hiểm và - nếu ô an toàn.
Dòng thứ ba mô tả vách phải theo định dạng tương tự.

Đảm bảo ô thứ $1$ của vách trái là an toàn.

Dữ liệu ra

In ra YES nếu ninja có thể thoát khỏi hẻm núi, ngược lại in NO.

Ràng buộc

$1 \leq n, k \leq 10^{5}$ .
Mỗi xâu mô tả vách chỉ chứa các ký tự X và -.

Ví dụ

Input	Output	Giải thích
7 3 ---X--X -X--XX-	YES	Ninja nhảy sang vách phải (lên ô $4$ ), leo xuống ô $3$ , nhảy sang vách trái (lên ô $6$ ), nhảy lần nữa lên ô $9 > 7$ — thoát.
6 2 --X-X- X--XX-	NO	Không tồn tại chiến lược nào để ninja thoát trước khi bị nước nhấn chìm.

Bình luận

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