The MTM Machine

The MTM is one of the first digital machines ever designed. The aim of the machine is to process positive integer numbers, but due to the primitive nature of the machine only some numbers are accepted for processing; such numbers are called acceptable. When a number is accepted by MTM, the machine outputs another number, according to the rules stated below. When a number is not accepted, the machine simply outputs NOT ACCEPTABLE.

A number is a non empty string of decimal digits. Given two numbers N and M, when we write NM we mean the number formed by the digits of N followed immediately by the digits of M. For example, if N is 856 and M is 112 then NM is 856112. For any number X, the associate of X is the number X2X. For example, the associate of 78 is 78278.

We say that a number X produces a number Y, if number X is acceptable and when given as input to the machine MTM, the number returned by the machine is Y.

The behaviour of the MTM machine is governed by the following rules:

Rule 0:

A number containing the digit 0 (zero) is not acceptable.

Rule 1:

Given any number X not containing a digit zero, then number 2X produces X. For example, 234 produces 34.

Rule 2:

Given any pair of numbers X, Y, if X produces Y then 3X produces the associate of Y. For example, 25 produces 5 by Rule 1, so 325 produces 525.

Rule 3:

No other numbers are acceptable.

Your task here is to write a program that simulates the MTM machine.

Input 

The input file contains a set of test cases. Each test case appears in a separate line, and consists of a single positive number N, N < 10³², to be processed by the MTM machine. The file ends with a line containing the number 0 that should not be processed.

You may assume that the largest number output by the machine has at most 1000 digits.

Output 

For each test case, your program should write one line with the output produced by the machine if the corresponding number is acceptable; otherwise your program should write NOT ACCEPTABLE.

Sample Input 

20
22
42
32
33289
0

Sample Output 

NOT ACCEPTABLE
2
NOT ACCEPTABLE
NOT ACCEPTABLE
89289289289

---

Miguel A. Revilla
2000-02-09

十分討厭這種題目，其一原因是很難明白操作，其二是難以理解的英文語法。

題目說明 X produces a number Y，如果 X 是可被接受的，則 return Y

X, Y are not empty.

RULE0: 不能有數字 0 在其中
RULE1: 如果符合 2X 的型態，則 return X
RULE2: 如果符合 3X 的型態，則 return Y2Y。Y 來於 X return 什麼。
RULE3: others

要稍為判斷一下 RULE3 的 Y 不可為 empty，但在 RULE1 的 return X 有可能會是 empty.

基於以上幾點，用遞迴判斷很方便，但是很慢。

---

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

string MTM(string str) {
    if(str == "")
        return string("N");
    if(str[0] == 'N')
        return str;
    for(int i = 0; i < str.length(); i++)
        if(str[i] == '0')
            return string("N");
    if(str[0] == '2')
        return str.substr(1);
    if(str[0] == '3') {
        string Y = MTM(str.substr(1));
        if(Y == "")
            return "N";
        return Y + "2" + Y;
    }
    return "N";
}
int main() {
    char s[105];
    while(scanf("%s", s) == 1) {
        if(!strcmp(s, "0"))
            break;
        string ret = MTM(s);
        if(ret[0] == 'N')
            cout << "NOT ACCEPTABLE" << endl;
        else
            cout << ret << endl;
    }
    return 0;
}