ZeroJudge A521: Calculating Yuan Fen

UVa 12414 – Calculating Yuan Fen

"Yuanfen" is a Chinese term that is difficult for foreigners to understand. Generally speaking, yuanfen is a kind of force that mysteriously brings two people (usually lovers) together. Despite being a form of superstition, many people—especially women—like to calculate it.

Unfortunately, my girlfriend is like that too. One day, she asked me, "Honey, can you calculate our yuanfen?" Sigh, I really hate this question, but I can't refuse. Fortunately, I am a programmer, so I just need to find a good-looking algorithm and write a yuanfen calculator. After searching the internet for a few hours, I decided to adopt the following yuanfen algorithm:

Step 1: Extract the initials of the names and concatenate them. For example, if the lovers are named Jiang Yun Fan and Tang Yu Rou, their initials would be JYFTYR. 

Step 2: Replace each letter with a numeric string. Use ST to replace A, ST+1 to replace B, ST+2 to replace C, and so on, up to ST+25 to replace Z, where ST is a known positive integer. For example, if ST=81, then A is replaced with 81, B with 82, and so on, up to Z being replaced with 106. In the example above, JYFTYR would be replaced with 901058610010598.

Step 3: Repeat the following process: Add each pair of adjacent digits and write down the unit digit of the sum. It is easy to see that each time this operation is performed, the numeric string will have one less digit. Stop this process when the number becomes 100 or fewer digits. The resulting number is the yuanfen of the two people. Using the example above, the process is as follows:

901058610010598
91153471011547
0268718112691
284589923850
02937815135
2120596648
332545202
65799722
1268694
384453
12898
3077
374
01

So if ST=81, the yuanfen of Jiang Yun Fan and Tang Yu Rou would be only 1.

Oh no, I know my girlfriend well, and I know that even if the result is 99, she would still be unhappy. Can you find an ST that makes the yuanfen between my girlfriend and me 100? 

Sample Inputs/Outputs

Thought Process

Run a loop from 1 to 10000 to check each ST value. When calculating the yuanfen value for one of them, you can record the string that appears during this process. Use a map to record the results of the strings that have already appeared, so if the same string is encountered later, you don't need to recalculate and can directly find the answer.

Sample Code－ZeroJudge A521: Calculating Yuan Fen

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<string, int>MAP;

int calc(const string str) {
    if (str.length() <= 2 || str == "100") return stoi(str);
    if (MAP[str] != 0) return MAP[str];
    string newstr = "";
    for (int i = 0; i<str.length()-1; i++) {
        const int a = int(str[i] - '0'), b = int(str[i+1] - '0');
        newstr += (a+b)%10 + '0';
    }
    MAP[str] = calc(newstr);
    return MAP[str];
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string str;
    while (cin >> str) {
        bool ok = false;
        for (int i = 1; i<=10000; i++) {
            string add = "";
            for (int j = 0; j<str.length(); j++) {
                add += to_string(i + (str[j] - 'A'));
            }
            const int ans = calc(add);
            if (ans == 100) {
                cout << i << "\n";
                ok = true;
                break;
            }
        }
        if (!ok) cout << ":(\n";
    }
}

//ZeroJudge A521
//Dr. SeanXD