COCI 2020/2021 - Contest 3 - Knjige

View as PDF

Submit solution

Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020/2021 - Contest 3
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Tin là một cậu bé rất đặc biệt. Cậu ấy không thích nhiều thứ, chẳng hạn như đội bóng Barcelona, bị đánh bại trong trò chơi điện tử hoặc bất kì sự bừa bãi nào...

Hôm nay, cậu ấy đến thăm người bạn Ante của mình để phân thắng bại trong trò chơi FIFA. Tuy nhiên, ngay khi bước vào phòng của Ante, cậu ấy đã cảm thấy cực kì khó chịu. Ante có hai kệ sách nằm cạnh nhau trên tường: kệ bên trái chứa ~n~ cuốn sách về vô số thành tích của Barcelona được xếp chồng lên nhau, còn kệ bên phải thì để trống.

Lí do khiến Tin khó chịu không phải là vì cậu ấy không thích những cuốn sách về Barcelona của Ante, mà là vì những cuốn sách đó được sắp xếp một cách rất bừa bãi (chúng không được sắp xếp từ mỏng nhất đến dày nhất). Để chiều lòng bạn mình, Ante vội vàng sắp xếp lại kệ sách theo ý muốn của Tin. Trong mỗi bước, cậu ấy có thể thực hiện một trong hai hành động:

  • lấy cuốn sách trên cùng của một trong hai kệ bằng tay trái hoặc tay phải (chỉ có thể nếu tay đó đang không cằm cuốn sách nào khác)
  • đặt cuốn sách cậu ấy đang cầm ở một trong hai tay lên trên cùng của một trong hai kệ

Điểm mạnh của Ante là bóng đá chứ không phải sắp xếp sách, vì vậy cậu ấy muốn nhờ bạn tìm một cách sắp xếp gồm từng bước, sao cho sau khi thực hiện xong tất cả các cuốn sách sẽ nằm ở kệ bên trái và được sắp xếp từ mỏng nhất đến dày nhất, theo thứ tự từ trên xuống dưới.

Input

Dòng đầu tiên chứa một số nguyên ~n~ ~(1 \leq n \leq 100)~, số lượng sách nằm ở kệ bên trái.

Dòng thứ hai chứa ~n~ số nguyên ~d_{i}~ ~(1 \leq d_{i} \leq 1000)~ thể hiện độ dày của mỗi cuốn sách, theo thứ tự từ trên xuống dưới.

Output

Dòng đầu tiên in ra một số nguyên ~k~ ~(0 \leq k \leq 100\:000)~, số lượng bước trong cách sắp xếp của bạn.

Trong ~k~ dòng tiếp theo in ra từng bước theo định dạng ~\texttt{"{INSTRUCION} {HAND} {SHELF}"}~ (hành động - tay - kệ):

  • ~\texttt{{INSTRUCTION}}~: ~\texttt{UZMI}~ if nếu Ante cần lấy sách từ kệ, hoặc ~\texttt{STAVI}~ nếu cậu ấy cần đặt sách lên kệ (Trong tiếng Croatia, uzmi nghĩa là lấy, stavi nghĩa là đặt)
  • ~\texttt{{HAND}}~: ~\texttt{L}~ nếu hành động này được thực hiện bằng tay trái, hoặc ~\texttt{D}~ nếu bằng tay phải. (Trong tiếng Croatia, lijevo nghĩa là trái, desno nghĩa là phải)
  • ~\texttt{{SHELF}}~: ~\texttt{L}~ nếu hành động này được thực hiện ở kệ bên trái, hoặc ~\texttt{D}~ nếu ở kệ bên phải.

Bạn không cần phải tìm cách sắp xếp với độ dài ngắn nhất, nhưng số lượng bước không được vượt quá ~100\:000~. Có thể chứng minh được rằng luôn tồn tại một cách sắp xếp thỏa mãn các ràng buộc trên.

Sample 1

Input
3
2 3 1
Output
8
UZMI L L
STAVI L D
UZMI L L
UZMI D L
STAVI L L
UZMI L D
STAVI L L
STAVI D L
Giải thích

Sample 1

Sample 2

Input
4
1 1 2 5
Output
0

Comments

Please read the guidelines before commenting.


There are no comments at the moment.