trang chủ / đề bài / icpcwf22_u

Đườ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 90 độ. 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 đoạn ray thẳng và một đoạn ray cong

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 90 độ. 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 s và c: số đoạn ray thẳng và số đoạn ray cong hiện có (0≤s≤105, 4≤c≤105).

Dữ liệu ra

In ra một vòng tàu dùng không quá s đoạn thẳng và không quá c đ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 n, in ra một xâu gồm n 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

  • 0≤s≤105.
  • 4≤c≤105.

Ví dụ

Input Output Giải thích
4 12 LSRLLRLSLSRLLSRL Dùng hết 4 đoạn thẳng và 12 đoạn cong, xem hình bên dưới.
1 5 LLLL Không thể dùng đúng 1 đoạn thẳng hay đúng 5 đoạn cong; vòng dài nhất là 4 đoạn cong xếp thành hình vuông 2×2.

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 5, cột 4 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

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