a598. CPE：To Add or to Multiply (UVa 1101)

題目描述

a-C-m 處理器只有兩種指令：A 將目前整數加上 a；M 將目前整數乘以 m。

請寫出最短的指令程式，使任何輸入 x ∈ [p,q] 執行後，都得到 y ∈ [r,s]。若有多個同樣長的程式，將完整指令視為 A、M 組成的字串，選字典順序最小者（A 排在 M 前）。

輸入格式

每行有六個整數 a、m、p、q、r、s，皆介於 1 到 10^9，且 p ≤ q、r ≤ s。六個 0 表示結束，不需處理。

輸出格式

每筆輸出 Case k: 結果。若不需任何操作，結果為 empty；若無解，為 impossible。

其他情況以連續相同指令的次數壓縮表示，例如 3A 2M 1A，各段以空白分隔。每段次數必須為正，A 與 M 段交替出現。最短與字典順序均以未壓縮的指令字串判定。

題目來源：UVa 1101 — To Add or to Multiply。 原題：https://onlinejudge.org/external/11/1101.pdf