|
||||||||||
To Add or to MultiplyTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 270 Accepted Submission(s): 62 Problem Description The Industrial Computer Processor Company offers very fast, special purpose processing units tailored to customer needs. Processors of the a-C-mfamily (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. Sample Input
Sample Output
Source | ||||||||||
|