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 AB 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ự FB, nếu Oiram không thể nhảy tới đích bạn hãy xuất ra 1.

Subtask

30% số test có 1f,b,s,d,trL, 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ó 1f,b,s,d,trL, tổng của L trên tất cả các test con không quá 106.

Ví dụ

Đầu vào:

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

Đầu ra:

Copy
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.