Output

For each test case, first print the test case number, followed by the k^t^hcharacter after processing the initial word up to n^th step.

Sample Input

Output for Sample Input

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;
}

我要檢舉

#12596#Recursive Texting#遞迴

台長： Morris

您可能對以下文章有興趣

[ACM-ICPC] 5725 - Fun Coloring

[UVA][Tree] 11350 - Stern-Brocot Tree

[UVA] 12406 - Help Dexter

[UVA] 10573 - Geometry Paradox

人氣(2,732) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][greedy] 12545 - Bits Equalizer
此分類上一篇:[UVA][math] 10287 - Gifts in a Hexagonal Box

回應(0)