Bạn có một robot trên một xa lộ vô tận hướng Đông-Tây, và nó cần giao một chiếc bánh. Cứ mỗi dặm dọc theo xa lộ, về cả hai hướng, đều có một cột đèn. Bạn muốn lập trình cho robot di chuyển chính xác \(N\) cột đèn về phía Đông và để lại chiếc bánh ở đó. Lộ trình không nhất thiết phải đi thẳng, miễn là cuối cùng robot để lại bánh đúng vị trí.

Thật không may, robot chỉ được trang bị bộ nhớ rất hạn chế và không có logic nâng cao. Để điều khiển robot, bạn phải cung cấp cho nó một chương trình rất đơn giản ngay từ đầu. Chương trình này phải bao gồm một hoặc nhiều câu lệnh, mỗi câu lệnh cho robot biết phải làm gì trong những điều kiện nhất định. Các câu lệnh này phải có định dạng sau:

<S> <M> -> <action>

Điều này có nghĩa là nếu tất cả các điều kiện sau được đáp ứng:

1. Robot đang ở trạng thái S.
2. Robot đang ở một cột đèn được đánh dấu bằng số M.

Thì nó sẽ thực hiện chính xác một trong các hành động sau:

1. Đánh dấu cột đèn hiện tại bằng một số mới, thay đổi trạng thái và di chuyển. Để thực hiện việc này, action phải có định dạng "D NS NM", trong đó D là hướng di chuyển (W cho hướng Tây và E cho hướng Đông), NS là trạng thái mới của robot và NM là dấu mới cho cột đèn hiện tại.
2. Để lại bánh tại vị trí hiện tại và tự hủy. Để thực hiện việc này, action phải có định dạng "R".

Nếu bạn đưa ra hai hoặc nhiều câu lệnh có cùng giá trị S và M, robot sẽ hoạt động sai và làm hỏng bánh.

Nếu tại bất kỳ thời điểm nào robot ở trạng thái \(X\) tại một cột đèn được đánh dấu \(Y\) mà không có câu lệnh nào với \(S=X\) và \(M=Y\), robot sẽ bối rối và ăn mất bánh.

Tất cả các trạng thái và dấu đánh phải là số nguyên có giá trị tuyệt đối không quá một triệu (\(10^6\)). Giả sử ban đầu robot ở trạng thái \(0\) và tất cả các cột đèn đều được đánh dấu bằng số \(0\).

Cho \(N\), hãy viết một chương trình để robot để lại bánh đúng nơi quy định. Chương trình của bạn phải sử dụng tối đa \(30\) câu lệnh và phải kết thúc trong vòng \(X\) bước.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bao gồm một dòng duy nhất chứa một số nguyên \(N\), cho biết cột đèn nơi robot phải để lại bánh.

Dữ liệu ra

Đối với mỗi bộ test, trước tiên hãy in ra "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng câu lệnh bạn sẽ sử dụng. Tiếp theo in ra y dòng, mỗi dòng đại diện cho một câu lệnh cho robot theo định dạng đã mô tả ở trên.

CẢNH BÁO: Phản hồi của giám khảo có thể mất nhiều hơn bình thường khoảng 5 giây vì đầu ra của bạn được chạy như một phần của quá trình xác thực.

Ràng buộc

• \(1 \le T \le 15\).

Phân nhóm

• Test set 1 (Visible): \(0 \le N \le 500\); \(X = 250,000\) (\(2.5 \times 10^5\)).
• Test set 2 (Hidden): \(0 \le N \le 5000\); \(X = 150,000\) (\(1.5 \times 10^5\)).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
0
4
0

Case #1: 1
0 0 -> R
Case #2: 5
0 0 -> E 1 1
1 0 -> E 2 1
2 0 -> E 3 1
3 0 -> E -1 1
-1 0 -> R
Case #3: 3
0 0 -> E 1 1
0 1 -> R
1 0 -> W 0 1

Nguồn

Google Code Jam 2011, Chung kết thế giới, bài Program within a Program.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.