Problem A
To Add or to Multiply
Problem ID: addmul
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 → 3 → 4 → 5 → 10), while the 5-C-3 processor yields 51 with the same program and input
(2 → 7 → 12 → 17 → 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 p, q, r, 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 p, q, r, and s, your job is to construct the shortest a-C-m program which,
for every input x such that p ≤ x ≤ q, yields some output y such that r ≤ y ≤ 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.
Input
The input contains several test cases. Each test case is given by a line with the six integers a, m, p, q, r, and s as
described above (1 ≤ a, m, p, q, r, s ≤ 10
9
, p ≤ q and r ≤ s).
The last test case is followed by a line with six zeros.
Output
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 n consecutive M operations.
Follow the format of the sample output.
ICPC 2011 World Finals Problem A: To Add or to Multiply
