11058 - Encoding

[Martin Macko]

This problem looks simple, but with this code, I get RE.
Someone can explain me what's wrong?
The test case above gives correct result.

You have too short array for the input string.

........char string[22]; ........<-- set it to something like 110
........char encoded[22];
........char subst[26][102];
........int c = 1;

........while(scanf("%s%*[\n]", string) == 1){
..............
........}

[leocm]

The correct output:

Code: Select all

Case #1: The encoding string is aabbaa.



Your code outputs one 'a' less.

Martin, my output for this case it's the same that yours, "aabbaa".
Test again and look... What is wrong?
Anyone knows?

Thank you!

[Martin Macko]

Martin, my output for this case it's the same that yours, "aabbaa".
Test again and look... What is wrong?
Anyone knows?

Thank you!

I guess you are working on a windows machine, aren't you? If so, think about writing portable code as the OJ is running on linux. On linux your code throws away the last char of the input string. Note that while windows use "\r\n" to mark end of line all unixes use just "\n" to mark it.

[A1]

I got a lots of WA a on this easy looking problem ~x(
but cann't find the cause..
may be some of u can help me to find out the cause.
here is my code and some test cases...

Code: Select all

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;

#define All(X) X.begin(),X.end()
#define co continue
#define re return
#define ox 2147483647
struct ToCh{
   int f;
   char tc[28];
};
struct inCh{
   int i;
   char a, b;
};
bool comp(inCh a,inCh b){
   re a.i<b.i;
}
int main(){
   char word[110],toch[28],x[5],y[5];
   int i,j,n,siz,next,k,cas=1,l;
   vector<ToCh>update;
   vector<inCh>temp;
   inCh R;
   ToCh T;
   //freopen("11058.txt","r",stdin);
   //freopen("11058.out","w",stdout);
   while(scanf("%s",word)==1){
      for(i=0;i<26;i++){
         scanf("%s",x);
         toch[i]=x[0];
      }
      toch[i]='\0';
      scanf("%d",&n);
      update.clear();
      temp.clear();
      siz=0;
      for(j=0;j<n;j++){
         scanf("%d %s %s",&i, x,y);
         R.i=i;R.a=x[0];R.b=y[0];
         temp.push_back(R);
      }
      sort(All(temp),comp); //this sort may be unnecessay, but i consider it to sure
      k=-1;
      for(l=0;l<n;l++){
         //scanf("%d %s %s",&i, x,y);
         i=temp[l].i;
         x[0]=temp[l].a;
         y[0]=temp[l].b;
         if(i!=k){
            k=T.f=i;
            for(j=0;j<26;j++){
               T.tc[j]=-1;
            }
            T.tc[x[0]-'a']=y[0];
            update.push_back(T);            
            siz++;
         }else{
            update[siz-1].tc[x[0]-'a']=y[0];
         }
      }      
      if(k!=-1)
         next=update[0].f;
      else next=-1;
      k=0;
      for(i=0;word[i]!='\0';i++){
         if(i==next && k<siz){
            for(j=0;j<26;j++){
               x[0]=update[k].tc[j];
               if(x[0]!=-1){
                  toch[j]=x[0];
               }
            }
            k++;
            next=update[k].f;
         }
         word[i]=toch[word[i]-'a'];
      }
      printf("Case #%d: The encoding string is %s.\n\n",cas++,word);
   }
   return 0;
}


I test this with the following inputs

Code: Select all

aaab
b
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
5
0 a a
1 a b
2 a c
3 b d
4 x y

abcd
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
5
0 a z
1 a y
2 a x
3 a w
4 x y

aaaa
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
5
0 a z
1 a y
2 a x
3 a w
4 x y

baba
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
4
0 b a
1 a b
1 b x
2 a x

aaaaaa
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
2
2 a b
4 a a

ufrn
t
o
w
k
q
z
f
n
y
i
c
m
s
j
n
r
g
l
d
s
u
s
g
y
e
u
14
0 q t
0 j f
1 v d
1 r o
1 f d
1 r o
1 f a
2 e p
2 r w
2 v e
2 f x
3 y p
3 t m
3 u k

abcdisdbcaront
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
0

abcdisdbcaront
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
7
0 a x
0 a w
0 b h
1 d t
2 c a
4 c e
10 t g



the output of this code is:

Code: Select all

Case #1: The encoding string is abcd.

Case #2: The encoding string is zaaa.

Case #3: The encoding string is zyxw.

Case #4: The encoding string is abxx.

Case #5: The encoding string is aabbaa.

Case #6: The encoding string is uawj.

Case #7: The encoding string is abcdisdbcaront.

Case #8: The encoding string is whatisthewrong.



[Martin Macko]

I got a lots of WA a on this easy looking problem ~x(
but cann't find the cause..
may be some of u can help me to find out the cause.
here is my code and some test cases...

Your I/Os are correct, but your solution isn't working for the following input:

Code: Select all

wskghe
p
x
d
d
v
w
y
n
l
i
l
t
x
y
m
o
y
q
y
q
f
m
d
x
o
z
20
0 a l
0 f j
0 g u
0 g u
0 g w
0 g w
0 h p
0 i z
0 n f
0 n g
0 n q
0 p p
0 r w
0 u e
0 u o
0 u u
0 v i
0 w a
0 w e
0 w m



The correct output:

Code: Select all

Case #1: The encoding string is mylwpv.



[A1]

Thanks Martin . I got AC..

[Martin Macko]

Thanks Martin . I got AC..

After getting AC, please, remove the code from your previous post

[Mushfiqur Rahman]

Thanks for Martin Macko. I got Ac now
The wrong was in my algo. [img][/img]

[Martin Macko]

Thanks for Martin Macko. I got Ac now
The wrong was in my algo. [img][/img]

After getting AC, please, remove your code from your posts...

[algoJo]

can anybody give me some hints, I've got WA all the times...
I've checked my program with I/O sets in this board and it's OK.

Code: Select all

#include<stdio.h>
#include<string.h>
#define max 1000

char kata[max];
char enc1[max];
char arr[27];

void compute(void){
   int i,len;
   len=strlen(kata);
   for(i=0;i<len;i++)
      enc1[i]=arr[kata[i]-'a'];
}

void init(void){
   memset(kata,0,sizeof(kata));
   memset(enc1,0,sizeof(enc1));
   memset(arr,0,sizeof(arr));
}

void main(){
   int i,len,R,p,k,cas=0;
   char a,b,line[max];
   while(gets(kata))
   {
   if(strlen(kata)==0) gets(kata);
    if(cas) printf("\n");
   cas++;
   len=strlen(kata);
   for(i=0;i<26;i++)
   {
      gets(line);
      sscanf(line,"%c",&arr[i]);
   }
   compute();
   memset(line,0,sizeof(line));
   gets(line);
   sscanf(line,"%d",&R);
   memset(line,0,sizeof(line));
   for(i=0;i<R;i++)
   {
      gets(line);
      sscanf(line,"%d %c %c",&p,&a,&b);
      for(k=0;k<len;k++)
         if(k>=p)
         {
            if(kata[k]==a) enc1[k]=b;
         }
   }
   enc1[len]=0;
   printf("Case #%d: The encoding string is %s.\n",cas,enc1);
   init();
   }
}


[Mushfiqur Rahman]

Thanks for Martin for his helpful sample. Lastly I found my bug and got AC

[GoLuckyBall]

The following is my code.

In Online Judge, it must run 3's.But limit of the time is 1's, please help me what should I improve my code. Thanks!!

#include<iostream>
#include<string>
using namespace std;

int main() {
int count = 1;
string S;
cin >> S;
while ( S != "EOF" ) {
char Letter[26];
for ( int i=0; i<26; i++ )
cin >> Letter[i];

int CaseNum;
string rule2[1000][3];
cin >> CaseNum;
for ( int i=0; i<CaseNum; i++ )
for ( int j=0; j<3; j++ )
cin >> rule2[i][j];

for ( int i=0; i<S.length(); i++ ) {
char temp;
temp = Letter[int(S[i])-97];
for ( int j=i; j>=0; j-- )
if ( atoi(rule2[j][0].c_str()) <= i )
if ( rule2[j][1][0] == S[i] )
temp = rule2[j][2][0];
S[i] = temp;
}
cout << "Case #" << count << ": The encoding string is " << S << "." << endl << endl;
count++;
cin >> S;
}

system("pause");
return 0;
}

[Fahim]

I don't know why everyone is saying this problem is easy . I have been trying to understand the given sample I/O for 2 days and still don't get it .Could anyone please explain the sample I/O

[outsbook]

I explain the sample input output, then the problem is very clear for understand.

Original string: ufrn

a replace by: t
b replace by: o
c replace by: w
d replace by: k
e replace by: q
f replace by: z
g replace by: f
h replace by: n
i replace by: y
j replace by: i
k replace by: c
l replace by: m
m replace by: s
n replace by: j
o replace by: n
p replace by: r
q replace by: g
r replace by: l
s replace by: d
t replace by: s
u replace by: u
v replace by: s
w replace by: g
x replace by: y
y replace by: e
z replace by: u

1. encoding the first char 'u'. Now position is: 0
a. Apply the rules which p=0 to encoding strategy. (i.e use the rule [0 q t], [0 j f]
After use the rule the encoding strategy like this.
a replace by: t
b replace by: o
c replace by: w
d replace by: k
e replace by: q
f replace by: z
g replace by: f
h replace by: n
i replace by: y
j replace by: f
k replace by: c
l replace by: m
m replace by: s
n replace by: j
o replace by: n
p replace by: r
q replace by: t
r replace by: l
s replace by: d
t replace by: s
u replace by: u
v replace by: s
w replace by: g
x replace by: y
y replace by: e
z replace by: u
b. Now encode the character 'u' using encode strategy. In encode strategy 'u' replace by 'u'.

2. Encoding the second char 'f'. Now position is: 1
a. Apply the rules which p=1 to encoding strategy. (i.e use the rule [1 v d], [1 f d], [1 r o])
After use the rule the encoding strategy like this.
a replace by: t
b replace by: o
c replace by: w
d replace by: k
e replace by: q
f replace by: d
g replace by: f
h replace by: n
i replace by: y
j replace by: f
k replace by: c
l replace by: m
m replace by: s
n replace by: j
o replace by: n
p replace by: r
q replace by: t
r replace by: o
s replace by: d
t replace by: s
u replace by: u
v replace by: d
w replace by: g
x replace by: y
y replace by: e
z replace by: u
b. Now encode the character 'f' using encode strategy. In encode strategy 'f' replace by 'd'.

3. Encoding the second char 'r'. Now position is: 2
a. Apply the rules which p=2 to encoding strategy. (i.e use the rule [2 e p], [2 v e])
After use the rule the encoding strategy like this.
a replace by: t
b replace by: o
c replace by: w
d replace by: k
e replace by: p
f replace by: d
g replace by: f
h replace by: n
i replace by: y
j replace by: f
k replace by: c
l replace by: m
m replace by: s
n replace by: j
o replace by: n
p replace by: r
q replace by: t
r replace by: o
s replace by: d
t replace by: s
u replace by: u
v replace by: e
w replace by: g
x replace by: y
y replace by: e
z replace by: u
b. Now encode the character 'r' using encode strategy. In encode strategy 'r' replace by 'o'.

4. Encoding the second char 'n'. Now position is: 3
a. Apply the rules which p=3 to encoding strategy. (i.e use the rule [3 y p], [3 t m], [3 u k])
After use the rule the encoding strategy like this.
a replace by: t
b replace by: o
c replace by: w
d replace by: k
e replace by: p
f replace by: d
g replace by: f
h replace by: n
i replace by: y
j replace by: f
k replace by: c
l replace by: m
m replace by: s
n replace by: j
o replace by: n
p replace by: r
q replace by: t
r replace by: o
s replace by: d
t replace by: m
u replace by: k
v replace by: e
w replace by: g
x replace by: y
y replace by: p
z replace by: u
b. Now encode the character 'n' using encode strategy. In encode strategy 'r' replace by 'j'.