Đường ray tàu đồ chơi
Đề bài
Mô tả
Mọi đứa trẻ, và cả khá nhiều người lớn, đều mê tàu hoả đồ chơi. Từ chiếc tàu "xình xịch" của trẻ mới biết đi cho tới mô hình đường sắt công phu chiếm trọn cả tầng hầm của người chơi lâu năm, đây là một ngành kinh doanh có lãi. Công ty Xây dựng Đường ray Tàu đồ chơi (TTTCC) sản xuất đường ray cho mọi lứa tuổi và mọi trình độ. Để giữ chân khách hàng cũ và có thể thu hút thêm khách mới, gần đây TTTCC bắt đầu phát hành các bản thiết kế hướng dẫn cách nối các đoạn ray thành những đường tàu phức tạp.
Thông thường, một nhà thiết kế nghĩ ra một đường tàu thú vị, rồi công bố cả bản thiết kế lẫn số lượng từng loại đoạn ray (chẳng hạn đoạn cong và đoạn thẳng) cần dùng để lắp nó. Nhưng TTTCC mới phát hiện ra rằng nhiều khách hàng lại muốn điều ngược lại: họ đã có sẵn một đống đoạn ray (có thể tìm thấy trên gác xép nhà bà), và muốn dùng chúng để lắp một đường tàu thật lớn. Việc này khó đến mức nào?
Để nghiên cứu khả năng tự động hoá việc thiết kế, TTTCC muốn lắp đường tàu từ hai loại đoạn ray: đoạn thẳng và đoạn cong độ. Hình dưới minh hoạ một đoạn ray thẳng (bên trái) và một đoạn ray cong (bên phải), mỗi đoạn nằm trong một ô vuông: đoạn thẳng nối hai cạnh đối diện của ô, đoạn cong nối hai cạnh kề nhau của ô.

Một đường tàu hợp lệ được tạo bằng cách đặt các đoạn ray lên một lưới ô vuông, mỗi đoạn chiếm đúng một ô của lưới. Cả hai loại đoạn ray đều có thể xoay một góc là bội của độ. Một đường tàu "đúng nghĩa" phải liên thông và tạo thành một vòng khép kín duy nhất. Cho số đoạn ray thẳng và số đoạn ray cong hiện có, hỏi vòng khép kín dài nhất có thể lắp được là bao nhiêu?
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và : số đoạn ray thẳng và số đoạn ray cong hiện có (, ).
Dữ liệu ra
In ra một vòng tàu dùng không quá đoạn thẳng và không quá đoạn cong, có độ dài (tính bằng số đoạn ray được dùng) lớn nhất có thể dưới ràng buộc này. Vòng phải khép kín và không được tự cắt (không có hai đoạn ray nào nằm cùng một ô). Nếu có nhiều vòng cùng độ dài lớn nhất, in vòng nào cũng được.
Nếu vòng có độ dài , in ra một xâu gồm ký tự, mỗi ký tự là một đoạn ray theo thứ tự gặp phải khi đi hết một vòng. Ký tự S là một đoạn thẳng, L là một đoạn cong rẽ trái, R là một đoạn cong rẽ phải.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 12 | LSRLLRLSLSRLLSRL | Dùng hết đoạn thẳng và đoạn cong, xem hình bên dưới. |
| 1 5 | LLLL | Không thể dùng đúng đoạn thẳng hay đúng đoạn cong; vòng dài nhất là đoạn cong xếp thành hình vuông . |
Vòng của ví dụ thứ nhất (mỗi ô ghi loại đoạn ray đặt ở ô đó, đường màu cam là đường tàu chạy qua các ô theo thứ tự trong xâu, bắt đầu từ ô ở hàng , cột và đi lên trên):
grid . L S L . . S . R L L R . R L L S R S . . . L L . path orange 5,4 4,4 3,4 3,5 2,5 2,4 1,4 1,3 1,2 2,2 3,2 3,1 4,1 4,2 4,3 5,3 5,4
Bình luận