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 kthcharacter 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
剛開始做這題的時候，真是一點思路也沒有，後來想到搜，但是總是超時，找解題報告也找不到，這是一道近段時間Uva比賽中的題目，做過的人很少。過了幾天後，突然搜到國內網站有的oj 加了這道題，並且有人過了，有人的代碼是可以share的，我就看了一下， 看完之後我感覺這道題目好經典啊，這可能是我做過的中的最高端的了啊。思想懂了以後就開始弄代碼，最後還是調了好久，從昨天一直調到現在，終於ac了。
好了，這下可以安心睡覺了。 acmer們晚安。
[cpp]
#include <stdio.h>
#include <string.h>
#include <math.h>
long long int dp[20][30];
char s1[200],c;
int n,m,pt[30],flag;
char s2[10][10]={"ZERO","ONE","TWO","THREE","FOUR","FIVE","SIX",
"SEVEN","EIGHT","NINE"};
int main()
{
void Init();
void solve(char str[100],int devel);
void deal_dp(int x, int y);
int i,j,t,tem=1;
Init();
scanf("%d",&t);
while(t--)
{
scanf("%s %d %d",s1,&n,&m);
flag=0;
solve(s1,n);
printf("Case %d: %c\n",tem++,c);
}
return 0;
}
void deal_dp(int x,int y)
{
int l,i;
if(dp[x][y]>0)
{
return ;
}
l=strlen(s2[x]);
if(y==1)
{
dp[x][y]=(long long int)l;
return ;
}
for(i=0;i<=l-1;i++)
{
deal_dp(pt[s2[x][i]-'A'+1],y-1);
dp[x][y]+=dp[pt[s2[x][i]-'A'+1]][y-1];
}
}
void Init()
{
char str;
int i,j;
for(i='A';i<='Z';i++)
{
str=(char)i;
if(str>='A'&&str<='C')
{
pt[str-'A'+1]=2;
}else if(str>='D'&&str<='F')
{
pt[str-'A'+1]=3;
}else if(str>='G'&&str<='I')
{
pt[str-'A'+1]=4;
}else if(str>='J'&&str<='L')
{
pt[str-'A'+1]=5;
}else if(str>='M'&&str<='O')
{
pt[str-'A'+1]=6;
}else if(str>='P'&&str<='S')
{
pt[str-'A'+1]=7;
}else if(str>='T'&&str<='V')
{
pt[str-'A'+1]=8;
}else if(str>='W'&&str<='Z')
{
pt[str-'A'+1]=9;
}
}
memset(dp,0,sizeof(dp));
for(i=2;i<=9;i++)
{
for(j=1;j<=21;j++)
{
deal_dp(i,j);
}
}
}
void solve(char str[100],int devel)
{
int i,j,l;
int Str;
if(flag)
{
return ;
}
if(devel==0)
{
c=str[m-1];
flag=1;
return ;
}
l=strlen(str);
for(i=0;i<=l-1;i++)
{
Str=str[i]-'A'+1;
if(dp[pt[Str]][devel]>=m)
{
solve(s2[pt[Str]],devel-1);
}else
{
m-=dp[pt[Str]][devel];
}
}
}
