# Problem C: Babelfish

Problem C: Babelfish

## Problem C: Babelfish

You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.

Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters. Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as "eh".

``````dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay
``````

``````cat
eh
loops
``````

``````#include <cstdio>
#include <cstring>
const int maxn=100000+10;
const int maxs=10+5;
char dict[maxn][2][maxs];
int n;
bool isblank(char s[])
{
int k=strlen(s);
while(--k>=0)
if(s[k]>='a'&&s[k]<='z')
return false;
return true;
}
void swap(char a[],char b[])
{
char t[maxs];
strcpy(t,a);
strcpy(a,b);
strcpy(b,t);
}
void sort(int a,int b,char s[][2][maxs])
{
if(a>=b)
return;
char t[maxs];
strcpy(t,s[(a+b)/2][1]);
int i,j;
i=a-1,j=b+1;
do
{
do
++i;
while(strcmp(t,s[i][1])>0);
do
--j;
while(strcmp(t,s[j][1])<0);
if(i<j)
{
swap(s[i][0],s[j][0]);
swap(s[i][1],s[j][1]);
}
}while(i<j);
sort(a,j,s);
sort(j+1,b,s);
}
int find(char s[])
{
int l,r;
l=0;
r=n;
while(l+1<r)
{
int mid=(l+r)/2;
if(strcmp(dict[mid][1],s)<=0)
l=mid;
else
r=mid;
}
if(strcmp(dict[l][1],s))
return -1;
return l;
}
int main()
{
char s[maxs+maxn];
n=0;
gets(s);
while(!isblank(s))
{
sscanf(s,"%s%s",dict[n][0],dict[n][1]);
++n;
gets(s);
}
sort(0,n-1,dict);
while(scanf("%s",s)!=EOF)
{
int k=find(s);
if(k<0)
printf("%s\n","eh");
else
printf("%s\n",dict[k][0]);
}
return 0;
}``````

``````#include <stdio.h>
#include <stdlib.h>

struct ddd {
char eng[12], pig[12];
} d[100000];

int nd, i,j,k;
char buf[10000];

compar(struct ddd *a, struct ddd *b) {
return strcmp(a->pig, b->pig);
}

main(){
while (gets(buf) && buf[0]) {
sscanf(buf,"%s %s",d[nd].eng,d[nd].pig);
nd++;
}
qsort(d,nd,sizeof(struct ddd),compar);
while (gets(buf)) {
struct ddd b, *p;
strcpy(b.pig,buf);
p = bsearch(&b,d,nd,sizeof(struct ddd),compar);
if (p != NULL) printf("%s\n",p->eng);
else printf("eh\n");
}
}``````