Nhảy bước (Task I)


Submit solution

Points: 3.2 (partial)
Time limit: 0.5s
JAVA11 1.0s
Pypy 3 1.0s
Memory limit: 67M
JAVA11 977M
Pypy 3 977M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Trong trò chơi \(ABC\), bản đồ là một đường tròn được chia thành \(L\) mốc, các mốc được đánh thứ tự từ \(1\) tới \(L\) theo chiều kim đồng hồ. Ví dụ với \(L = 12\), bản đồ trò chơi là:

Nhân vật Oiram trong trò chỉ nhảy lên được \(f\) bước (xuôi chiều kim đồng hồ) hoặc nhảy về \(b\) bước (ngược chiều kim đồng hồ). Ví dụ với \(L = 12, f = 3, b = 2\), Oiram đang đứng ở vị trí \(1\) thì khi nhảy lên một lần, nhảy xuống một lần vị trí của cậu lần lượt là \(4, 11\). Đặc biệt, có những vị trí đặt bẫy mà Oiram không được phép nhảy vào.

Cho trước các giá trị \(L, f, b\), vị trí Oiram đang đứng \(s\) - start, vị trí điểm đích \(d\) - destination, và các vị trí bẫy. Kí hiệu \(F\) là nhảy lên, \(B\) là nhảy về. Bạn hãy tìm một cách để Oiram nhảy từ \(s\) tới \(d\) nếu có thể. Nếu có nhiều cách nhảy thỏa mãn thì Oiram sẽ chọn cách có thứ tự từ điển nhỏ nhất.

Ghi chú: Bộ \(A\) nhỏ hơn bộ \(B\) theo thứ tự từ điển khi một trong hai điều kiện sau được thỏa mãn:

  • Cỡ bộ \(A\) nhỏ hơn cỡ bộ \(B\).
  • Tại vị trí đầu tiên mà phần tử của \(A\) và \(B\) khác nhau, phần tử của \(A\) nhỏ hơn \(B\).

Đầu vào

Dòng đầu chứa số tự nhiên \(t\), số lượng test con. Mỗi bộ test được mô tả như sau:

  • Dòng đầu tiên chứa \(6\) số nguyên dương: \(L, f, b, s, d, tr\).
  • (Nếu \(tr > 0\)) Dòng tiếp theo chứa \(tr\) số nguyên dương trong khoảng \([1, L]\) là vị trí của các bẫy.

Ghi chú: Vị trí các bẫy có thể trùng nhau, và được đảm bảo khác \(s\).

Đầu ra

Với mỗi test con, xuất ra kết quả trên một dòng là một xâu chỉ chứa toàn kí tự \(F\) và \(B\), nếu Oiram không thể nhảy tới đích bạn hãy xuất ra \(-1\).

Subtask

\(30\%\) số test có \(1 \le f, b, s, d, tr \le L\), tổng của \(L\) trên tất cả các test con không quá \(2000\).

\(70\%\) số test còn lại có \(1 \le f, b, s, d, tr \le L\), tổng của \(L\) trên tất cả các test con không quá \(10^6\).

Ví dụ

Đầu vào:

3
10 3 2 7 6 0
10 3 2 7 6 2
10 5
10 3 2 7 6 0

Đầu ra:

BBF
-1
BBF

Trong test con thứ nhất, chú ý rằng với cách nhảy \(BFB\) Oiram cũng nhảy được từ vị trí \(7\) tới vị trí \(6\) nhưng \(BBF\) \(<\) \(BFB\) nên \(BBF\) là kết quả đúng.

QDUY

Comments

There are no comments at the moment.