Thoát khỏi mê cung
Đề bài
Mô tả
Bạn bị bắt cóc và bị bỏ lại trong một mê cung bí ẩn. Trong lúc tuyệt vọng tìm đường ra, bạn tình cờ nhặt được một mảnh giấy nhỏ ghi những ký hiệu lạ. Vì một phần mảnh giấy đã bị xé mất, bạn không thể biết xâu ký tự ban đầu. Tuy vậy, trên mảnh giấy vẫn còn bốn số nguyên và . Bạn nhận ra rằng chúng là số lần xuất hiện của bốn ký tự L, R, U và D trong một xâu bí ẩn:
- : số lần xuất hiện của ký tự L.
- : số lần xuất hiện của ký tự R.
- : số lần xuất hiện của ký tự U.
- : số lần xuất hiện của ký tự D.
Trên mảnh giấy còn có một số nguyên rất lớn ().
Bạn đoán rằng đây hẳn là manh mối do một người từng bị mắc kẹt trong mê cung trước bạn để lại. Sau khi nghiên cứu kỹ thông điệp lạ, cuối cùng bạn cũng giải mã được nó.
Một đường đi trong mê cung được biểu diễn bằng một xâu chỉ gồm bốn ký tự L, R, U và D (L: đi sang trái; R: đi sang phải; U: đi lên; D: đi xuống). Đường thoát phải dùng đúng bước L, bước R, bước U và bước D. Manh mối không cho biết trực tiếp thứ tự các bước. Thay vào đó, đường thoát là xâu thứ theo thứ tự từ điển trong số tất cả các xâu phân biệt có thể tạo ra bằng cách sắp xếp lại các bước này. Khi so sánh theo thứ tự từ điển, các ký tự được sắp theo thứ tự: L < R < U < D.
Yêu cầu: Hãy tìm đường thoát. Nếu có ít hơn đường đi phân biệt, in ra .
Dữ liệu vào
Một dòng duy nhất gồm bốn số nguyên (, ) và một số nguyên ().
Dữ liệu ra
In ra đường thoát: xâu phân biệt thứ theo thứ tự từ điển được tạo bởi đúng ký tự L, ký tự R, ký tự U và ký tự D.
Nếu số xâu phân biệt tạo được ít hơn , in ra .
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 1 1 1 3 | LURD | Các xâu theo thứ tự là LRUD, LRDU, LURD, ... nên xâu thứ là LURD. |
| 1 2 1 1 50 | DLRUR | Có xâu phân biệt. xâu đầu tiên bắt đầu bằng L, R hoặc U; xâu thứ là xâu thứ trong các xâu bắt đầu bằng D. |
| 1 2 1 1 61 | -1 | Chỉ có xâu phân biệt, ít hơn . |
| 1 0 1 1 5 | DLU | Sáu xâu theo thứ tự là LUD, LDU, ULD, UDL, DLU, DUL. |
Bình luận