Robot tuyết

Đ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

Bạn có một robot di chuyển trên lưới vô hạn. Robot bắt đầu ở ô $(0, 0)$ và thực hiện một dãy lệnh là xâu $s$ gồm các ký tự L, R, U, D.

L: di chuyển từ $(x, y)$ sang $(x - 1, y)$ .
R: di chuyển từ $(x, y)$ sang $(x + 1, y)$ .
U: di chuyển từ $(x, y)$ sang $(x, y + 1)$ .
D: di chuyển từ $(x, y)$ sang $(x, y - 1)$ .

Một dãy lệnh được gọi là hợp lệ nếu:

Robot xuất phát từ $(0, 0)$ và kết thúc tại $(0, 0)$ .
Robot không bao giờ đi vào cùng một ô khác $(0, 0)$ quá một lần.
Ô $(0, 0)$ được thăm tối đa hai lần (lúc bắt đầu và lúc kết thúc); nếu dãy lệnh rỗng thì $(0, 0)$ chỉ được thăm một lần.

Vì xâu $s$ ban đầu có thể không hợp lệ, bạn được phép:

Xoá đi một số (có thể là tất cả hoặc không) lệnh trong $s$ ,
Sau đó sắp xếp lại các lệnh còn lại theo thứ tự tuỳ ý.

Nhiệm vụ: tìm cách xoá ít lệnh nhất có thể (tức là giữ lại nhiều lệnh nhất có thể) sao cho sau khi sắp xếp lại, dãy thu được là hợp lệ. In ra dãy lệnh có độ dài lớn nhất tìm được. Nếu có nhiều đáp án, in ra bất kỳ.

Bạn phải trả lời $q$ truy vấn độc lập.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $q$ — số truy vấn.
$q$ dòng tiếp theo, mỗi dòng chứa một xâu $s$ gồm các ký tự L, R, U, D.

Dữ liệu ra

Với mỗi truy vấn, in ra trên hai dòng:

Dòng 1: số nguyên $k$ — số lệnh được giữ lại lớn nhất.
Dòng 2: xâu $t$ độ dài $k$ — dãy lệnh hợp lệ thu được. Nếu $k = 0$ , bạn có thể in ra dòng trống hoặc bỏ qua dòng thứ hai.

Nếu có nhiều đáp án thoả mãn, in ra một đáp án bất kỳ.

Ràng buộc

$1 \leq q \leq 2 \cdot 10^{4}$ .
$1 \leq | s | \leq 10^{5}$ .
Tổng độ dài tất cả các xâu $s$ không vượt quá $10^{5}$ .

Ví dụ

Input	Output	Giải thích
6 LRU DURLDRUDRULRDURDDL LRUDDLRUDRUL LLLLRRRR URDUR LLL	2 LR 14 LLLUUUURRRDDDD 12 LLLUUURRRDDD 2 LR 2 UD 0	Truy vấn 1: giữ một `L` và một `R`, đi qua $(- 1, 0)$ rồi quay về. Truy vấn 2: lấy $3$ `L`, $4$ `U`, $3$ `R`, $4$ `D` → đi vòng quanh hình chữ nhật $3 \times 4$ . Truy vấn 4: chỉ có `L` và `R`, chọn 1 cặp → độ dài 2. Truy vấn 5: lấy 1 `U` và 1 `D` (không có `L`/`R` để ghép) → độ dài 2. Truy vấn 6: chỉ có `L`, không tạo được chu trình → 0.

Bình luận

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