[UVA][遞迴] 12596 - Recursive Texting
Problem E
Recursive Texting
All of you have typed in mobile phones. In this problem, you will have to do a similar thing.
You are given a word. You will have to process it. There are two phases in each step.
Type the given word using standard mobile keyboard, that is, press the digit containing the required letter once.
Convert each digit found in the first phase into word, concatenate those words, and produce a new word.
For example, if you are asked to type DHAKA.
Step 1, phase 1:
34252
Step 1, phase 2:
THREEFOURTWOFIVETWO
Step 2, phase 1:
8473336878963483896
Step 2, phase 2:
EIGHTFOURSEVENTHREETHREETHREESIXEIGHTSEVENEIGHTNINESIXTHREEFOUREIGHTTHREEEIGHTNINESIX
And so on….
Your job is to find the kth character after nth step.
Input
First line of input will consist of number of test cases, T (1 <= T <= 1000). Each of the next T lines contains the initial word, W (1 <= |W| <= 100), n(1<=n<=20), k (1 <= k <= 10^9), separated by a space. n will be such that kth character is always found. The initial word will contain only uppercase letter of English alphabet and no space within it.
Output
For each test case, first print the test case number, followed by the kth character after processing the initial word up to nth step.
|
Sample Input |
Output for Sample Input |
|
4 DHAKA 1 1 DHAKA 2 1 DHAKA 1 5 DHAKA 2 10
|
Case 1: T Case 2: E Case 3: E Case 4: S |
Note
Spellings of the digits:
0 – ZERO, 1 – ONE, 2 – TWO, 3 – THREE, 4 – FOUR, 5 – FIVE, 6 – SIX, 7 – SEVEN, 8 – EIGHT, 9 – NINE
Problemsetter: Anna Fariha, Shiplu Hawlader
Special Thanks: Md. Mahbubul Hasan
題目描述：
根據手機按鍵，一次轉換為「將字串轉換成數字，再將每個數字依照英文讀法展開。」
求轉換 n 次後的第 k 個字元。
題目解法：
設計 3 個 function()。
1. calcChar():從一個 char 轉換 n 次後，會得到多少 char。
2. calcNum() :從一個 digit 轉換 n 次後，會得到多少 char。
3. solve() :求解的 function 接收原本的字串, n, k。
遞迴關係：
calcChar(char, n) = calcNum(digit, n);//映射手機號碼
calcNum(digit, n) = sigma(calcChar(char, n-1));//映射轉換英文數字
solve(char w[], n, k) 比較複雜一點，需要調用 calcChar 和自己本身。
嘗試將 w[i] 計算轉換 n 回不超過 k，如果超過則遞迴該字元。請參照 code 的寫法。
#include <stdio.h>
#include <string.h>
char typeNum[] = "22233344455566677778889999";
char strNum[10][10] = {"ZERO","ONE","TWO","THREE","FOUR","FIVE",
"SIX","SEVEN","EIGHT","NINE"};
long long dp1[26][50], dp2[10][50];
long long calcNum(int,int);
long long calcChar(char c, int step) {
c -= 'A';
if(step == 0) return 1;
if(dp1[c][step] != -1) return dp1[c][step];
long long &ret = dp1[c][step];
return ret = calcNum(typeNum[c]-'0', step);
}
long long calcNum(int digit, int step) {
if(dp2[digit][step] != -1) return dp2[digit][step];
long long &ret = dp2[digit][step];
ret = 0;
for(int i = 0; strNum[digit][i]; i++)
ret += calcChar(strNum[digit][i], step-1);
return ret;
}
char solve(char w[], int n, long long k) {
if(n == 0)
return w[k-1];
for(int i = 0; w[i]; i++) {
long long generate = calcChar(w[i], n);
if(generate < k) {
k -= generate;
} else {
return solve(strNum[typeNum[w[i]-'A']-'0'], n-1, k);
}
}
}
int main() {
memset(dp1, -1, sizeof(dp1));
memset(dp2, -1, sizeof(dp2));
int testcase, cases = 0;
int n, i, j;
char w[105];
long long k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%s %d %lld", w, &n, &k);
printf("Case %d: %c\n", ++cases, solve(w, n, k));
}
return 0;
}