trang chủ / đề bài / icpc26_mt_d

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 a1,a2,a3 và a4. 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:

  • a1: số lần xuất hiện của ký tự L.
  • a2: số lần xuất hiện của ký tự R.
  • a3: số lần xuất hiện của ký tự U.
  • a4: 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 k (1≤k≤109).

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 a1 bước L, a2 bước R, a3 bước U và a4 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ứ k 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 k đường đi phân biệt, in ra −1.

Dữ liệu vào

Một dòng duy nhất gồm bốn số nguyên a1,a2,a3,a4 (0≤a1,a2,a3,a4≤104, 1≤a1+a2+a3+a4≤104) và một số nguyên k (1≤k≤109).

Dữ liệu ra

In ra đường thoát: xâu phân biệt thứ k theo thứ tự từ điển được tạo bởi đúng a1 ký tự L, a2 ký tự R, a3 ký tự U và a4 ký tự D.

Nếu số xâu phân biệt tạo được ít hơn k, in ra −1.

Ràng buộc

  • 0≤a1,a2,a3,a4≤104.
  • 1≤a1+a2+a3+a4≤104.
  • 1≤k≤109.

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ứ 3 là LURD.
1 2 1 1 50 DLRUR Có 5!2!=60 xâu phân biệt. 48 xâu đầu tiên bắt đầu bằng L, R hoặc U; xâu thứ 50 là xâu thứ 2 trong các xâu bắt đầu bằng D.
1 2 1 1 61 -1 Chỉ có 60 xâu phân biệt, ít hơn k=61.
1 0 1 1 5 DLU Sáu xâu theo thứ tự là LUD, LDU, ULD, UDL, DLU, DUL.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0