726 - Decode

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse »

oh my goodness.

I changed:

vector ==> array
Character.(tolower/toupper) ==> +- 32
print ==> write


now it got accepted in
time:1.506 mem:10688
jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse »

hey darko, wanna see my code? I did exactly what you said and it got accepted now. I didn't change the way I did I/O at all.


From your last statement, it sounded like you think my program is continuously waiting for input, and that's why it's TLE.

Just for the record, I tried submitting my program with a system.exit(1) right after I do all the input, and the autojudge returned WA. So that's when I figured it couldn't have been my input that's causing TLE
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

No, that's fine, now I have to solve it, too :)

No, what I meant was *my* code seems to be in an endless loop on the second string.

[EDIT] There, I feel better now :)
scan33scan33
New poster
Posts: 4
Joined: Mon Dec 04, 2006 5:39 am
Contact:

726 ~ in C WA need help

Post by scan33scan33 »

I have tried a lot of cases and got them all right.
Can anyone give me help?

Below is my code......

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

struct CHARS{
char item;
int num;
};

typedef struct CHARS CHS;

int cmp(const void *a1, const void *a2)
{
if(((CHS*)a1)->num < ((CHS*)a2)->num)
return 1;
if(((CHS*)a1)->num == ((CHS*)a2)->num)
if(((CHS*)a1)->item > ((CHS*)a2)->item)
return 1;
else
return 0;
return (-1);
}

int main()
{
CHS s_org[30],s[30],tmp;
char ch,trans[256],s1[10000],s2[30][5000];
int slen1,slen2[100],at,i,j,k,sr2=0,t=0,all=0;

while(slen1!=0 || t==0)
{
gets(s1);
slen1 = strlen(s1);
if(slen1==0 && t==1)
break;
if(slen1>0)
t=1;
for(at=0;at<slen1;at++)
{
if(isalpha(s1[at]))
{
ch = tolower(s1[at]);
for(i=0;i<all;i++)
{
if(s_org.item == ch)
{
s_org.num += 1;
break;
}
}
if(i==all)
{
s_org[all].item = ch;
s_org[all].num = 1;
all+=1;
}
}
}/*store*/
}

qsort(s_org,all,sizeof(CHS),cmp);

while(1)
{
if(gets(s2[sr2])==NULL)
break;
slen2[sr2] = strlen(s2[sr2]);
if(slen2[sr2]==0)
break;
++sr2;
}

all = 0;

for(k=0;k<sr2;k++)
{
for(at=0;at<slen2[k];at++)
{
if(isalpha(s2[k][at]))
{
ch = tolower(s2[k][at]);
for(i=0;i<all;i++)
{
if(s.item == ch)
{
s.num += 1;
break;
}
}
if(i==all)
{
s[all].item = ch;
s[all].num = 1;
all+=1;
}
}
}/*store*/
}

qsort(s,all,sizeof(CHS),cmp);

for(j=0;j<all;j++)
{
trans[s[j].item] = s_org[j].item;
}

for(k=0;k<sr2;k++)
{
for(at=0;at<slen2[k];at++)
{
if(isalpha(s2[k][at]))
{
ch = s2[k][at];
if(isupper(ch))
{
ch = tolower(ch);
ch = trans[ch];
ch = toupper(ch);
printf("%c",ch);
}
else
{
ch = trans[ch];
printf("%c",ch);
}
}
else
printf("%c",s2[k][at]);
}
if(k!=sr2-1)
printf("\n");
}
/*scanf(" ");*/
return 0;
}
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Dont open a new thread unless there is none. Try the following thread
http://online-judge.uva.es/board/viewto ... hlight=726
Ami ekhono shopno dekhi...
HomePage
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Post by algoJo »

Hi, I got multiple RE and MLE on this problem, can someone show me some hints?

Code: Select all

#include<cstdlib>
#include<cstdio>
#include<cstring>
#define MAX 40001

struct node{
   char alpha;
   int total;
}arr[26],rra[26];



char kar[]="abcdefghijklmnopqrstuvwxyz";
char coto[]="abcdefghijklmnopqrstuvwxyz";

char key[1000][MAX];
int I;

void count(char line[]){
   long int i,len;
   len=strlen(line);
   for(i=0;i<len;i++)
      if(line[i]>='A'&&line[i]<='Z')
      {
         line[i]-='A';
         line[i]+='a';
         arr[line[i]-'a'].total++;
      }
      else
      if(line[i]>='a'&&line[i]<='z')
      {
         arr[line[i]-'a'].total++;
      }
}


void count2(char line[]){
   long int i,len;
   len=strlen(line);
   for(i=0;i<len;i++)
      if(line[i]>='A'&&line[i]<='Z')
      {
         line[i]-='A';
         line[i]+='a';
         rra[line[i]-'a'].total++;
      }
      else
      if(line[i]>='a'&&line[i]<='z')
      {
         rra[line[i]-'a'].total++;
      }
}

void init(void){
   int i;
   for(i=0;i<26;i++)
   {
      arr[i].alpha=rra[i].alpha=i+'a';
      arr[i].total=rra[i].total=0;
   }
}

int cmp(const void *a,const void *b){
   struct node *x,*y;
   x=(struct node*)a;
   y=(struct node*)b;
   return y->total-x->total;
}

void doit(void){
   qsort(arr,26,sizeof(arr[0]),cmp);
   qsort(rra,26,sizeof(rra[0]),cmp);
   long int i,j;
   struct node temp;
   for(i=25;i>0;i--)
      for(int j=i-1;j>=0;j--)
         if(arr[i].total==arr[j].total&&arr[i].alpha<arr[j].alpha)
         {
            temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
         }  

   for(i=25;i>0;i--)
      for(int j=i-1;j>=0;j--)
         if(rra[i].total==rra[j].total&&rra[i].alpha<rra[j].alpha)
         {
            temp=rra[i];
            rra[i]=rra[j];
            rra[j]=temp;
         }     
   for(i=0;i<26;i++)
      if(rra[i].total)
      {
         coto[rra[i].alpha-'a']=arr[i].alpha;
      }      
   for(i=0;i<I;i++)
   {
      long int len=strlen(key[i]);
      for(int j=0;j<len;j++)
         if(key[i][j]>='a'&&key[i][j]<='z'){printf("%c",coto[key[i][j]-'a']);}
         else
         if(key[i][j]>='A'&&key[i][j]<='Z'){printf("%c",coto[key[i][j]-'A']-32);}
         else printf("%c",key[i][j]);
      printf("\n");
   }
}

int main(){
   char line[MAX];
  // freopen("in.txt","r",stdin);
 //  freopen("out.txt","w",stdout);
   init();
   while(gets(line))
   {
      if(!strlen(line)) break;
      count(line);
      memset(line,0,sizeof(line));
   }
   while(gets(line))
   {
      strcpy(key[I],line);
      I++;
      count2(line);
      memset(line,0,sizeof(line));
   }
   doit();
}
DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re:

Post by DD »

algoJo wrote:Hi, I got multiple RE and MLE on this problem, can someone show me some hints?

Code: Select all

#include<cstdlib>
#include<cstdio>
#include<cstring>
#define MAX 40001

struct node{
   char alpha;
   int total;
}arr[26],rra[26];



char kar[]="abcdefghijklmnopqrstuvwxyz";
char coto[]="abcdefghijklmnopqrstuvwxyz";

char key[1000][MAX];
int I;

void count(char line[]){
   long int i,len;
   len=strlen(line);
   for(i=0;i<len;i++)
      if(line[i]>='A'&&line[i]<='Z')
      {
         line[i]-='A';
         line[i]+='a';
         arr[line[i]-'a'].total++;
      }
      else
      if(line[i]>='a'&&line[i]<='z')
      {
         arr[line[i]-'a'].total++;
      }
}


void count2(char line[]){
   long int i,len;
   len=strlen(line);
   for(i=0;i<len;i++)
      if(line[i]>='A'&&line[i]<='Z')
      {
         line[i]-='A';
         line[i]+='a';
         rra[line[i]-'a'].total++;
      }
      else
      if(line[i]>='a'&&line[i]<='z')
      {
         rra[line[i]-'a'].total++;
      }
}

void init(void){
   int i;
   for(i=0;i<26;i++)
   {
      arr[i].alpha=rra[i].alpha=i+'a';
      arr[i].total=rra[i].total=0;
   }
}

int cmp(const void *a,const void *b){
   struct node *x,*y;
   x=(struct node*)a;
   y=(struct node*)b;
   return y->total-x->total;
}

void doit(void){
   qsort(arr,26,sizeof(arr[0]),cmp);
   qsort(rra,26,sizeof(rra[0]),cmp);
   long int i,j;
   struct node temp;
   for(i=25;i>0;i--)
      for(int j=i-1;j>=0;j--)
         if(arr[i].total==arr[j].total&&arr[i].alpha<arr[j].alpha)
         {
            temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
         }  

   for(i=25;i>0;i--)
      for(int j=i-1;j>=0;j--)
         if(rra[i].total==rra[j].total&&rra[i].alpha<rra[j].alpha)
         {
            temp=rra[i];
            rra[i]=rra[j];
            rra[j]=temp;
         }     
   for(i=0;i<26;i++)
      if(rra[i].total)
      {
         coto[rra[i].alpha-'a']=arr[i].alpha;
      }      
   for(i=0;i<I;i++)
   {
      long int len=strlen(key[i]);
      for(int j=0;j<len;j++)
         if(key[i][j]>='a'&&key[i][j]<='z'){printf("%c",coto[key[i][j]-'a']);}
         else
         if(key[i][j]>='A'&&key[i][j]<='Z'){printf("%c",coto[key[i][j]-'A']-32);}
         else printf("%c",key[i][j]);
      printf("\n");
   }
}

int main(){
   char line[MAX];
  // freopen("in.txt","r",stdin);
 //  freopen("out.txt","w",stdout);
   init();
   while(gets(line))
   {
      if(!strlen(line)) break;
      count(line);
      memset(line,0,sizeof(line));
   }
   while(gets(line))
   {
      strcpy(key[I],line);
      I++;
      count2(line);
      memset(line,0,sizeof(line));
   }
   doit();
}
I noticed that in you cmp function, you didn't sort it alphabetically if x->total == y->total.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.
Post Reply

Return to “Volume 7 (700-799)”