a521 - 12414 - Calculating Yuan Fen
題目描述
題目描述了一個計算“緣份”的演算法，輸入為兩個人的姓名縮寫字串，目標是找到一個正整數 ST，使得經過演算法計算後得到的緣份值為 100。如果找不到這樣的 ST，或者 ST 大於 10000，則輸出 ":("。
解題思路
題目要求尋找一個 ST 值，使得經過一系列的轉換和計算後，最終結果為 100。程式碼採用了暴力搜尋的方法，從 ST = 1 開始，逐步增加 ST 的值，直到找到滿足條件的 ST 或者 ST 達到 10000。
對於每個 ST 值，程式碼首先將輸入字串中的每個字母轉換為對應的數字，然後進行迭代相加的過程，直到結果變成 100 或不超過兩位數。如果最終結果為 100，則輸出當前的 ST 值，並結束搜尋。
複雜度分析
- 時間複雜度: O(N * 10000 * M)，其中 N 是輸入字串的長度，10000 是 ST 的最大值，M 是數字字串的長度。最壞情況下，需要遍歷 10000 個 ST 值，並且對於每個 ST 值，需要對字串進行轉換和計算，時間複雜度與字串長度有關。
- 空間複雜度: O(M)，其中 M 是數字字串的長度。程式碼使用了一個固定大小的字串陣列
tmp來儲存數字字串，空間複雜度與字串長度有關。
程式碼
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
while(cin >> s){
int ST=0,i,tt;
bool k=1;
while(++ST<=10000&&k){
char tmp[101]={};
for(i=0,tt=0;s[i];++i) {
int num = (s[i]-'A')+ST;
sprintf(tmp+tt,"%d",num);
while(tmp[tt]!='\0')
++tt;
}
for(i=0;i<tt;++i)
tmp[i] -= '0';
while(tt>1){
for(i=0;i<tt-1;++i){
tmp[i]=tmp[i]+tmp[i+1];
if(tmp[i]>=10)tmp[i]-=10;
}
tt--;
if(tt==2&&tmp[0]==1&&tmp[1]==0&&tmp[2]==0){
cout<<ST<<"\n";
k=0;
break;
}
}
}
if(k)
puts(":(");
}
return 0;
}