Page 2 of 2

Posted: Sat Aug 12, 2006 7:29 pm
by Martin Macko
ytsejam wrote: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.
ytsejam main() wrote:........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){
..............
........}


Posted: Sun Aug 13, 2006 5:57 am
by 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!

Posted: Sun Aug 13, 2006 2:59 pm
by Martin Macko
leocm wrote: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.

Posted: Wed Aug 16, 2006 2:51 pm
by 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.


Posted: Wed Aug 16, 2006 10:03 pm
by Martin Macko
A1 wrote: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.


Posted: Wed Aug 16, 2006 10:18 pm
by A1
Thanks Martin :D. I got AC..

Posted: Wed Aug 16, 2006 10:20 pm
by Martin Macko
A1 wrote:Thanks Martin :D. I got AC..
After getting AC, please, remove the code from your previous post :)

Posted: Wed Aug 23, 2006 3:41 pm
by Mushfiqur Rahman
Thanks for Martin Macko. I got Ac now
The wrong was in my algo. [img][/img]

Posted: Wed Aug 23, 2006 9:00 pm
by Martin Macko
Mushfiqur Rahman wrote: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... :)

Posted: Sat Feb 03, 2007 1:18 am
by algoJo
can anybody give me some hints, I've got WA all the times... :roll:
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();
	}
}

Posted: Sat Mar 03, 2007 3:23 pm
by Mushfiqur Rahman
Thanks for Martin for his helpful sample. Lastly I found my bug and got AC

Posted: Sun Mar 02, 2008 9:07 am
by 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;

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

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

system("pause");
return 0;
}

Re: 11058 - Encoding

Posted: Sat Oct 02, 2010 6:08 pm
by Fahim
I don't know why everyone is saying this problem is easy :o . 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
:oops: :oops: :oops:

Re: 11058 - Encoding

Posted: Fri Jul 06, 2012 2:27 am
by 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'.