Bedao Mini Contest 15 - ROBOT

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Comments

Please read the guidelines before commenting.



  • -11
    sondeptrai1508   commented on Dec. 2, 2022, 9:43 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.