10282 - Babelfish

[mystical_liu]

[cpp]
/* @JUDGE_ID: 6983KT 10282 C++ */
#include<stdio.h>
#include<string.h>
#define max 100000
typedef struct dict
{
char in[20],dic[20];
}dict;
dict arr[max];
long count=0;
main()
{
char in1[20],in2[20];
int i,j,k,flag;
while(gets(in1))
{
if(!strlen(in1))break;
j=0;
for(i=0;i<strlen(in1);i++)
{if(in1[i]==' ')break;
else arr[count].in[j++]=in1[i];}
j=0;i++;
for(;i<strlen(in1);i++)
{if(in1[i]=='\0')break;
else arr[count].dic[j++]=in1[i];}
count++;
}
for(i=0;i<20;i++)in1[i]='\0';
while(gets(in1))
{
flag=0;
for(i=0;i<count;i++)
{
for(j=0;j<20;j++)in2[j]='\0';
strcpy(in2,arr[i].dic);
if(!(strcmp(in2,in1)))
{
printf("%s\n",arr[i].in);
flag=1; break;
}
}
if(!flag)printf("eh\n");
for(i=0;i<20;i++)in1[i]='\0';
}
}[/cpp]
this is my code and the judgement says time limite exceeded~is there any method can solve this problem???

[Dominik Michniewski]

I am not sure, that you handle input correctly ...
But try to use qsort and bsearch to find word in dictionary - this decrease complexity of search to log(num_words) from num_words ....

Dominik

[Eric]

I use Shell Sort and Binary Search to solve this problem.
I still need 9.4s to tackle it. I think optimization must be needed.

[zzylhy]

#include<iostream.h>
#include<string.h>
#include<stdio.h>


class node
{
public:
node();
~node(){};
char s[10],t[10];
node *next;
};

node::node()
{
int i;
for(i=0;i<11;i++)
{
s[i]='\0';
t[i]='\0';
}
}

node *creat()
{
node *h,*p,*q;
char u[22],ch;
h=new node();
p=h;
while(1)
{
q=new node();
q->s[0]=getchar();
if(q->s[0]!=10)
{
scanf("%s",u);
strcat(q->s,u);
scanf("%s",q->t);
p->next=q;
p=p->next;
}
else
{
break;
}
ch=getchar();
}
p->next=NULL;
return h;
}

void select(node *h,char t[11])
{
node *p;
p=h;
while((p!=NULL)&&(strcmp(p->t,t)!=0))
{
p=p->next;
}
if(p==NULL)
cout<<"eh"<<endl;
else
puts(p->s);
}

int main()
{
node *head;
char t[11];
head=creat();
while(1)
{
gets(t);
if(t[0]=='\0')
break;
select(head,t);
}
return 0;
}

I got TimeLimitExceeded.
Is there another way to solve it?

[anupam]

i haven't solved the problem but tried using avl tree and mapping of c++. it may help.

[Riyad]

my code for 10282 is very simple , i pushed the words into a array of structure. and than searched the array of structure linearly . as a result it takes a long time to search . is there any way i can decrease the execution time of the program by using any efficient searching algorithm like binary search.pliiiiiiiiiiiiiiiiiz help. here is my code:

Code: Select all

#include<stdio.h>
#include<string.h>

struct dictionary{
   
   char word[15],meaning[25];

};

struct dictionary obj[100001];

long int index=0;


int main(){

   char input[50];
   register long int i;
   int flag;
   freopen("input.in","rt",stdin);
   while(gets(input)){
   
      if(strcmp(input,"")==0)
         break;
      sscanf(input,"%s %s",obj[index].meaning,obj[index].word);
      index++;
      
   }
   

   while(gets(input)){
      flag=0;
      for(i=0;i<index;i++){
         if(strcmp(obj[i].word,input)==0){
            flag=1;
            puts(obj[i].meaning);
            break;
         
         }
         else
            continue;
      }
      if(flag==0){
         puts("eh");
      }
   }
   
   
   return 0;
}

looking for u r help .
Bye
Riyad

[Larry]

Sort and binary search.

[Riyad]

u told me to sort the arrays and binary search . i did as u said . but still i am having TLE . plizzzzzz help me in this prob
.here is my code:-

Code: Select all

#include<stdio.h>
#include<string.h>

struct dictionary{

   char word[15],meaning[25];

};

struct dictionary obj[100001];

long int index=0;
void sort(){
   register long int i ,j;
   struct dictionary temp;
   for(i=0;i<index;i++){
      for(j=i+1;j<index;j++){
         if(strcmp(obj[i].word,obj[j].word)>0){
            temp=obj[i];
            obj[i]=obj[j];
            obj[j]=temp;
         }
         else
            continue;
      }
   }

}
long int binsearch(char search[]){
   long int high,low,mid;
   
   low=0;
   high=index-1;
   while(low<=high){
      
      mid=(low+high)/2;

      if(strcmp(obj[mid].word,search)>0)
         high=mid-1;
      else if(strcmp(obj[mid].word,search)==0){
         
         return mid;
      }
      else
         low=mid+1;


   }
   
   return -1;


}


int main(){

   char input[50];
   long int bound;
   freopen("input.in","rt",stdin);
   while(gets(input)){

      if(strcmp(input,"")==0)
         break;
      sscanf(input,"%s %s",obj[index].meaning,obj[index].word);
      index++;

   }

   sort();
   
   while(gets(input)){
      
      bound=binsearch(input);
      if(bound!=-1){
         
         puts(obj[bound].meaning);
      }
      else{
         puts("eh");
      }
      
   }


   return 0;
}

Waiting for u r help . plizzzzzzzzz help.
Bye
Riyad

[UFP2161]

You should read up on the qsort() function in C .. Quick sort is O(n log n) while bubble sort is O(n^2) which is much too slow for this problem.

[Riyad]

i got ac using qsort . thanx for u r help buddy .it took about 1.027 second which was really amazing .

hey friend need a little a favour . i am a novice in here . i got a code of prime generator but dont know how to use it . hope u ll help me using it .
here is the code:

Code: Select all

#include<stdlib.h>
#include<malloc.h>

#define isprime(f,x) (*(f+(x)/16)&(1<<(((x)%16L)/2)))
#define setprime(f,x) *(f+(x)/16)|=1<<(((x)%16L)/2)

void main()
{
unsigned char *field=NULL,*zzz;
unsigned long teste=1,max,mom,count,alloc;
int d;
max=20010000L;

while(field==NULL)
zzz=field=(unsigned char*) malloc(alloc=(((max-=10000L)>>4)+1L));

for (count=0;count<alloc;count++)
*zzz++ = 0x00;

while((teste+=2)<max)
if(!isprime(field,teste))
for(mom=3L*teste;mom<max;mom+=teste<<1)
setprime(field,mom);
   if(isprime(field,3)==1)
/*now you can cll the module isprime to check any positive integer
either prime or not;
syntax:
isprime(field,integer);

if the module return 0 the integer will be prime
else not prime.

you can check upto 20000000 within a while
*/

free (field);
}

** my question is what will i use in place for field while calling the function isprime(). i understood that i ll use the integer which primality i am gonna check in place of the isprime(field,integer).give me an example plizzzzzzzzzzzzzzz.
Bye
Riyad

[Sanny]

Hello,
I've encountered a funny incident which I can not explain.

See the two codes of problem no 10282:

This got accepted :

[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define size 100005

struct dictionary
{
char foreign[12];
char eng[12];
}dict[size],*ptr;


int sort_f(const dictionary *a,const dictionary *b)
{
return (strcmp(a->foreign,b->foreign));
}


int main()
{
long int total=0;
char line[1000],temp[200];

while(gets(line))
{
if(line[0]=='\0')
break;

sscanf(line,"%s %s",dict[total].eng,dict[total].foreign);
total++; //note the second code
}
qsort(dict,total,sizeof(dict[0]),(int (*)(const void *,const void *))sort_f);

while(gets(temp))
{

ptr=(dictionary *)bsearch(temp,dict,total,sizeof(dict[0]),(int (*)(const void *,const void *))sort_f);

if(ptr)
printf("%s\n",(*ptr).eng);
else
printf("eh\n");

}

return 0;
}
[/cpp]

But this one didn't :

[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define size 100005

struct dictionary
{
char foreign[12];
char eng[12];
}dict[size],*ptr;


int sort_f(const dictionary *a,const dictionary *b)
{
return (strcmp(a->foreign,b->foreign));
}


int main()
{
long int total=0;
char line[1000],temp[200];

while(gets(line))
{
if(line[0]=='\0')
break;
sscanf(line,"%s %s",dict[total].eng,dict[total++].foreign);
//here's the only change
}
qsort(dict,total,sizeof(dict[0]),(int (*)(const void *,const void *))sort_f);

while(gets(temp))
{

ptr=(dictionary *)bsearch(temp,dict,total,sizeof(dict[0]),(int (*)(const void *,const void *))sort_f);

if(ptr)
printf("%s\n",(*ptr).eng);
else
printf("eh\n");

}

return 0;
}
[/cpp]

Can anyone explain it???

[..]

Code: Select all

sscanf(line,"%s %s",dict[total].eng,dict[total++].foreign);


In your code, you want the "++" operation to be executed after "total" is evaluated for twice. However, in the ANSI standard, it is not defined when will "++" operation executed in such statement.
The behaviour of such statment is compiler dependent.

[CDiMa]

Code: Select all

sscanf(line,"%s %s",dict[total].eng,dict[total++].foreign);


In your code, you want the "++" operation to be executed after "total" is evaluated for twice. However, in the ANSI standard, it is not defined when will "++" operation executed in such statement.
The behaviour of such statment is compiler dependent.

I think that Sanny was misleaded by the fact that side-effect are guaranteed to be completed after a sequence-point.
A sequence point is defined as:

* The call to a function, after the arguments have been evaluated.

* The end of the first operand of the following operators: logical AND &&; logical OR ||; conditional ? ; comma , .

* The end of a full expression: an initializer; the expression in an expression statement; the controlling expression of a selection statement (if or switch); the controlling expression of a while or do statement; each of the three expressions of a for statement; the expression in a return statement.

In his piece of code the sequence point at which the postdecrement of the variable total is completed is the call of the function sscanf. Athough there are commas between the variables passed to sscanf these *cannot* be considered as the "comma operator", hence the confusion.

Ciao!!!

Claudio

[someone]

ok, the code below is very simple, why do I get TLE for this

[cpp]#include <cstdio>
#include <map>
#include <string>
#include <iostream>
using namespace std;

map <string,string> rijecnik;
map <string,string>:: iterator iter;

char buffer[1000],ch[500],ch2[500];

int main ()
{
while (fgets(buffer,1000,stdin))
{
if (buffer[0]=='\n')break;
sscanf(buffer,"%s%s",ch,ch2);
rijecnik[ch]=ch2;
};
while (fgets(ch,1000,stdin))
{
sscanf(ch,"%s",buffer);
iter = rijecnik.find(buffer);
if (iter!=rijecnik.end())cout<<iter->second<<'\n';else cout<<"eh\n";
};
return 0;
};[/cpp]

[sunny]

some1 please explain me why i m gettin RTE for 10282. i didn't used the built-in bsearch here.