Đồng hồ cát

View as PDF

Submit solution

Points: 1.08 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cải tiến từ 1 bài thi UVA.

Đồng hồ cát có dạng 2 tam giác đều chung đỉnh, gồm ~2n-1~ dòng.

Lần lượt mỗi dòng có: ~n~ số, ~n-1~ số, ...., ~1~, ~2~, ..., ~n~ số ~(n < 21)~.

Mỗi ô ở dòng trên chỉ có thể di xuống ô phải dưới (R) hoặc ô trái dưới (L).

Yêu cầu:

Tìm đường đi có trọng số nhỏ nhất. Đường đi được mô tả là ô xuất phát ở hàng ~1~ (các ô được đánh số từ ~0~ tới ~n-1~) và chuỗi LR mô tả đường đi.

Cho số ~S \le 5000~, đếm số đường đi có trọng số ~S~ và mô tả đường đi có thứ tự từ điển nhỏ nhất ứng với ~S~.

Input

Dòng đầu tiên là 2 số ~n~ và ~S~.

~2n-1~ dòng tiếp theo số ~a~ mô tả đồng hồ cát. (~a \le 5000~)

Output

Gồm 4 dòng :

Trọng số nhỏ nhất từ hàng ~1~ tới hàng cuối .

Mô tả đường đi ứng với trọng số nhỏ nhất (nếu có nhiều đường đi, in ra đường đi có thứ tự từ điển nhỏ nhất)

Số đường đi có trọng số là ~S~. Nếu không có đường thì in ra ~-1~.

Đường đi ứng với trọng số ~S~ thỏa mãn.

Sample Input

3 17
1 2 3
4 5
6
5 4
3 2 1

Sample Output

16
0 RRRR
2
0 RRRL

Comments

Please read the guidelines before commenting.



  • 0
    madv809   commented on May 27, 2021, 4:10 a.m.

    Cuộc đời:))))))) Ngồi optimize sml tới 4h sáng, vừa AC xong mới nhớ ra để xử lý chuyện thứ tự từ điển nhỏ nhất thì lật cái bảng lại xong tham là được. Bạn nào TLE thì làm y chang tớ bảo nhé:vv