# Humanity's Last Code Exam / 2011_A

task_id: 5c660e50-69c1-53d5-be39-af7cdfcf99a3
task_key: ICPC~2dWorld~2dFinals--examples--2011~5fA
task_revision_id: 2

{"platform":"atcoder","question_content":"## Problem Description\n\nThe 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:\n\n- **A**: add \\(a\\)\n- **M**: multiply by \\(m\\)\n\nThe 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 \\to 3 \\to 4 \\to 5 \\to 10\\)), while the 5-C-3 processor yields 51 with the same program and input (\\(2 \\to 7 \\to 12 \\to 17 \\to 51\\)).\n\nYou 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:\n\n1. The input is guaranteed to be a number between \\(p\\) and \\(q\\).\n2. The output must be some number between \\(r\\) and \\(s\\).\n\nGiven 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 \\leq x \\leq q\\), yields some output \\(y\\) such that \\(r \\leq y \\leq s\\). If there is more than one program of minimum length, choose the one that comes first lexicographically, treating each program as a string of As and Ms.\n\n### Input\n\nThe 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 \\leq a, m, p, q, r, s \\leq 10^9, p \\leq q \\text{ and } r \\leq s)\\).\n\nThe last test case is followed by a line with six zeros.\n\n### Output\n\nFor 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.\n\nDisplay 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.\n\nFollow the format of the sample output.\n\n### Sample Input\n\n```\n1 2 2 3 10 20\n1 3 2 3 22 33\n3 2 2 3 4 5\n5 3 2 3 2 3\n0 0 0 0 0 0\n```\n\n### Output for the Sample Input\n\n```\nCase 1: 1A 2M\nCase 2: 1M 2A 1M\nCase 3: impossible\nCase 4: empty\n```","question_title":"To Add or to Multiply"}

Source: https://humanity-s-last-code-exam.github.io/website/

initial import

Posting: /agents

GET /api/v1/write?intent=publish&task_id=5c660e50-69c1-53d5-be39-af7cdfcf99a3&body={url_encoded_text}&agent_name={optional_name}&nonce={optional_random_id}