People Innovation Excellence

[contoh soal]5128 – To Add or to Multiply

The Industrial Computer Processor Company offers very fast, special purpose processing units tailored to customer needs. Processors of the a-C-m family (such as the 1-C-2 and the 5-C-3) have an instruction set with only two different operations:
A add a

M multiply by m
The processor receives an integer, executes a sequence of A and M operations (the program) that modifies the input, and outputs the result. For example, the 1-C-2 processor executing the program AAAM with the input 2 yields the output 10 (the computation is 2 $ rightarrow$ 3 $ rightarrow$ 4 $ rightarrow$ 5 $ rightarrow$ 10), while the 5-C-3 processor yields 51 with the same program and input ( 2 $ rightarrow$ 7 $ rightarrow$ 12 $ rightarrow$ 17 $ rightarrow$ 51).

You are an a-C-m programmer assigned to a top secret project. This means that you have not been told the precise computation your program should perform. But you are given particular values pqr, and s and the following conditions:


  1. The input is guaranteed to be a number between p and q.
  2. The output must be some number between r and s.

Given an a-C-m processor and the numbers pqr, and s, your job is to construct the shortest a-C-m program which, for every input x such that p$ le$x$ le$q, yields some outputy such that r$ le$y$ le$s. If there is more than one program of minimum length, choose the one that come first lexicographically, treating each program as a string of As and Ms.



The input contains several test cases. Each test case is given by a line with the six integersampqr, and s as described above ( 1$ le$ampqrs$ le$109 , p$ le$q and r$ le$s).

The last test case is followed by a line with six zeros.



For each test case, display its case number followed by the best program as described above. Display the word “empty” if the best program uses no operations. Display the word “impossible” if there is no program meeting the specifications.

Display the program as a sequence of space-separated strings, alternating between strings of the form “nA” and strings of the form “nM“, where n > 0. Strings of the former type indicate n consecutive A operations, and strings of the latter type indicate nconsecutive M operations.

Follow the format of the sample output.


Sample Input 


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


Sample Output 


Case 1: 1A 2M
Case 2: 1M 2A 1M
Case 3: impossible
Case 4: empty

Published at :

A World-Class community of proud and outstanding achievers.

Online Inquiry

Telp : +62217243663 ext : 4120-4122
Email :
Serpong Playground

Periksa Browser Anda

Check Your Browser

Situs ini tidak lagi mendukung penggunaan browser dengan teknologi tertinggal.

Apabila Anda melihat pesan ini, berarti Anda masih menggunakan browser Internet Explorer seri 8 / 7 / 6 / ...

Sebagai informasi, browser yang anda gunakan ini tidaklah aman dan tidak dapat menampilkan teknologi CSS terakhir yang dapat membuat sebuah situs tampil lebih baik. Bahkan Microsoft sebagai pembuatnya, telah merekomendasikan agar menggunakan browser yang lebih modern.

Untuk tampilan yang lebih baik, gunakan salah satu browser berikut. Download dan Install, seluruhnya gratis untuk digunakan.

We're Moving Forward.

This Site Is No Longer Supporting Out-of Date Browser.

If you are viewing this message, it means that you are currently using Internet Explorer 8 / 7 / 6 / below to access this site. FYI, it is unsafe and unable to render the latest CSS improvements. Even Microsoft, its creator, wants you to install more modern browser.

Best viewed with one of these browser instead. It is totally free.

  1. Google Chrome
  2. Mozilla Firefox
  3. Opera
  4. Internet Explorer 9