同題：UVa 12414 – Calculating Yuan Fen
緣份是一個外國人難以理解的中文名詞。大致說來，緣份是一種冥冥中將兩人 (通常是情人) 結合的力量。僅管是種迷信，很多人——特別是女生——喜歡去計算它。
不幸地，我的女友也是這樣。有天，她問我：「甜心，可以算一下我們的緣份嗎？」唉，我真的很討厭這問題，但我無法拒絕。還好，我是個程式設計師，所以我只要找到一個看來不錯的演算法並寫成一個緣份計算器就可以了。在網路上搜尋了幾個小時後，我決定採用以下的緣份演算法：
第一步：取出姓名的縮寫並接在一起。例如，如果這對戀人叫 Jiang Yun Fan 和 Tang Yu Rou，他們的縮寫就是 JYFTYR。
第二步：將每個字母以數字字串取代。用 ST 來取代 A，ST+1 來取代 B，ST+2 來取代 C，……，ST+25 來取代 Z，其中 ST 為一個已知的正整數。 例如，如果 ST=81，A 就以 81 來取代，B 就以 82 來取代，……，Z 則以 106 來取代。上面的例子，JYFTYR 則以 901058610010598 來取代。
第三步：重覆以下動作：將相鄰的兩位數相加，並寫下和的個位數。不難發現這個動作每做一次，這個數字字串就會少一位數。當這個數字變成 100 或是不超過兩位數時，便停止這個程序。所得的數字便是兩人的緣份。以上面的例子來說，處理的過程如下：
901058610010598
91153471011547
0268718112691
284589923850
02937815135
2120596648
332545202
65799722
1268694
384453
12898
3077
374
01
所以如果 ST=81，Jiang Yun Fan 和 Tang Yu Rou 的綠份便只有 1。
慘了，我很了解我的女友，我知道就算結果是 99 她仍然會不高興。你可以找到一個 ST 使得我和女友間的緣份會是 100 嗎？
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| EOF 輸入，最多 50 筆測。每筆測資有一個含有最少四個最多十個大寫字母的字串。 | 對於每筆測資，印出最小的正整數 ST (ST 不為零)。如果它不存在或是大於 10000，印出「:(」(不含引號)。 |
| JYFTYR ABCDEF YTHHLS YTHLML LYXM JYFLY CBTZX LXYZLE LXYLYR QWERTY | 148 634 🙁 910 96 4284 631 850 149 2277 |
解題思路
跑一個迴圈從 1 到 10000 去判斷每一個 ST 值，當計算出其中一個緣分值時，可以紀錄這個過程中出現的字串，使用 Map 來紀錄已經出現過的字串的結果，這樣子之後如果有遇到相同的字串就不需要再重新做計算可以直接找到答案。
範例程式碼－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