Bedao Mini Contest 15 - ROBOT

Xem dạng PDF

Gửi bài giải


Điểm: 0,40 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bé Đào là một người yêu thích sự sạch sẽ, ngăn nắp, nên đã quyết định chi tiền ra mua một con robot hút bụi đắt tiền về để giúp mình dọn dẹp nhà cửa.

Sàn nhà Bé Đào có thể mô tả như một mẳng phẳng hai chiều. Tại mỗi lượt di chuyển, từ vị trí ~(x, y)~ trên sàn nhà, robot có thể di chuyển sang trái đến ô ~(x, y-1)~, ~(x, y+1)~, ~(x+1, y)~ hoặc ~(x-1, y)~ tương ứng với bốn hướng trái, phải, lên, xuống.

Khi mới mua về, hành trình của robot được mặc định là một xâu kí tự độ dài ~n~ chỉ gồm bốn kí tự ~L~, ~R~, ~U~, ~D~ mô tả bốn hướng di chuyển. Bé Đào muốn nhà lúc nào cũng ngăn nắp cho nên Bé muốn thay đổi một số kí tự của hành trình sao cho sau khi dọn dẹp xong nhà, robot quay về đúng vị trí bắt đầu.

Tính số kí tự nhỏ nhất Bé cần thay đổi.

Input

  • Dòng đầu tiên chứa một số nguyên ~n~ là độ dài của hành trình của robot ~(1 \leq n \leq 10^5)~.

  • Dòng thứ hai chứa một xâu kí tự độ dài ~n~ chỉ chứa các kí tự ~L~, ~R~, ~U~, ~D~ mô tả hành trình ban đầu của robot.

Output

  • Một số nguyên duy nhất là số lượng kí tự nhỏ nhất Bé Đào cần thay đổi.

  • In ra ~-1~ nếu không tồn tại phương án thực hiện.

Subtask

  • ~20\%~ số test có ~n \leq 20~.

  • ~40\%~ số test khác có ~n \leq 5000~.

  • ~40\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

4
LLUD

Sample Output 1

1

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -15
    sondeptrai1508  đã bình luận lúc 2, Tháng 12, 2022, 2:43

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.