trang chủ / đề bài / icpcwf11_a

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ọ a-C-m (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 a;
  • M: nhân với m.

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 2 cho kết quả 10 (quá trình tính: 2→3→4→5→10), còn bộ xử lý 5-C-3 với cùng chương trình và đầu vào cho kết quả 51 (2→7→12→17→51).

Bạn là một lập trình viên a-C-m đượ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ị p, q, r, s 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ừ p tới q.
  • Kết quả phải là một số nằm trong đoạn từ r tới s.

Cho bộ xử lý a-C-m và các số p, q, r, s, hãy xây dựng chương trình a-C-m ngắn nhất sao cho với mọi đầu vào x thỏa mãn p≤x≤q, chương trình cho kết quả y thỏa mãn r≤y≤s. 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 a, m, p, q, r, s như mô tả ở trên.

Sau bộ test cuối cùng là một dòng gồm sáu số 0.

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 đó n>0. Xâu dạng thứ nhất biểu thị n phép A liên tiếp, xâu dạng thứ hai biểu thị n phép M liên tiếp.

Ràng buộc

  • 1≤a,m,p,q,r,s≤109.
  • p≤q và r≤s.

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 x thành 4(x+1), đưa 2 thành 12 và 3 thành 16, đều thuộc [10,20]. Bộ 2: MAAM biến x thành 3(3x+2), đưa 2,3 thành 24,33. Bộ 3: chương trình rỗng giữ nguyên 2<4; với đầu vào 3, cả A lẫn M đều cho 6>5, 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: m=1 nên phép M vô ích; AAA đưa [1,3] thành [7,9]. Bộ 2: AMA (1→2→4→5) và MMA (1→2→4→5) cùng dài 3, AMA đứng trước. Bộ 3: AAMAMA và MAMAMA đều cho 15 sau 6 phép, chọn AAMAMA. Bộ 4: AAM biến x thành 3(x+8), đưa [2,3] thành [30,33].

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