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 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)
