Cộng hay nhân
Đề bài
Mô tả
Công ty Industrial Computer Processor Company cung cấp các bộ xử lý chuyên dụng rất nhanh, thiết kế riêng theo nhu cầu khách hàng. Các bộ xử lý thuộc họ -C- (chẳng hạn 1-C-2 và 5-C-3) có tập lệnh chỉ gồm hai phép toán:
A: cộng thêm ;M: nhân với .
Bộ xử lý nhận vào một số nguyên, thực hiện một dãy các phép A và M (gọi là chương trình) để biến đổi số đó, rồi xuất ra kết quả. Ví dụ, bộ xử lý 1-C-2 chạy chương trình AAAM với đầu vào cho kết quả (quá trình tính: ), còn bộ xử lý 5-C-3 với cùng chương trình và đầu vào cho kết quả ().
Bạn là một lập trình viên -C- được giao một dự án tối mật. Vì thế bạn không được cho biết chính xác chương trình cần tính gì, mà chỉ được cho các giá trị , , , cùng các điều kiện sau:
- Đầu vào chắc chắn là một số nằm trong đoạn từ tới .
- Kết quả phải là một số nằm trong đoạn từ tới .
Cho bộ xử lý -C- và các số , , , , hãy xây dựng chương trình -C- ngắn nhất sao cho với mọi đầu vào thỏa mãn , chương trình cho kết quả thỏa mãn . Nếu có nhiều chương trình cùng độ dài nhỏ nhất, chọn chương trình đứng đầu theo thứ tự từ điển, coi mỗi chương trình là một xâu gồm các ký tự A và M.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test là một dòng chứa sáu số nguyên , , , , , như mô tả ở trên.
Sau bộ test cuối cùng là một dòng gồm sáu số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test theo sau là chương trình tốt nhất như mô tả ở trên, theo đúng định dạng Case i: <chương trình> của ví dụ. In từ empty nếu chương trình tốt nhất không có phép toán nào. In từ impossible nếu không có chương trình nào thỏa mãn yêu cầu.
Chương trình được in dưới dạng một dãy các xâu cách nhau bởi dấu cách, luân phiên giữa các xâu dạng nA và các xâu dạng nM, trong đó . Xâu dạng thứ nhất biểu thị phép A liên tiếp, xâu dạng thứ hai biểu thị phép M liên tiếp.
Ràng buộc
- .
- và .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 2 2 3 10 20 1 3 2 3 22 33 3 2 2 3 4 5 5 3 2 3 2 3 0 0 0 0 0 0 |
Case 1: 1A 2M Case 2: 1M 2A 1M Case 3: impossible Case 4: empty |
Bộ 1: AMM biến thành , đưa thành và thành , đều thuộc . Bộ 2: MAAM biến thành , đưa thành . Bộ 3: chương trình rỗng giữ nguyên ; với đầu vào , cả A lẫn M đều cho , nên mọi chương trình khác rỗng đều sai. Bộ 4: không cần phép toán nào. |
| 2 1 1 3 6 10 1 2 1 1 5 5 1 2 1 1 15 15 4 3 2 3 25 40 0 0 0 0 0 0 |
Case 1: 3A Case 2: 1A 1M 1A Case 3: 2A 1M 1A 1M 1A Case 4: 2A 1M |
Bộ 1: nên phép M vô ích; AAA đưa thành . Bộ 2: AMA () và MMA () cùng dài , AMA đứng trước. Bộ 3: AAMAMA và MAMAMA đều cho sau phép, chọn AAMAMA. Bộ 4: AAM biến thành , đưa thành . |
Bình luận