511  Do You Know the Way to San Jose?  Do nothing AC
Moderator: Board moderators
P200 : What's wrong with my program ?
#include<iostream.h>
#include<string.h>
void main()
{
char c[30], d[30], w[27], *c1, *d1;
int g[26][26], v[26], p[26], q[26], qh, qt, s1, s2, n;
for (; 1;)
{
cin >> c;
if (cin.fail()) break;
memset(g, 0, sizeof(g));
memset(v, 0xFF, sizeof(v));
memset(p, 0, sizeof(p));
n = 0;
if (*c == '#')
{
cout << endl;
continue;
}
for (cin >> d; *d != '#'; cin >> d)
{
for (c1 = c, d1 = d; *c1 && *d1 && *c1 == *d1; c1++, d1++);
if (*c1 && *d1)
{
if (v[*c1  'A'] == 1)
w[s1 = v[*c1  'A'] = n++] = *c1;
else
s1 = v[*c1  'A'];
if (v[*d1  'A'] == 1)
w[s2 = v[*d1  'A'] = n++] = *d1;
else
s2 = v[*d1  'A'];
g[s1][s2] = 1;
p[s2]++;
strcpy(c, d);
}
else if (!(*c1)) strcpy(c, d);
}
for (s2 = 0; p[s2]; s2++);
q[0] = s2;
for (qh = qt = 0; qh <= qt; qh++)
{
s1 = q[qh];
cout << w[s1];
for (s2 = 0; s2 < n; s2++)
if (g[s1][s2])
{
p[s2];
if (!p[s2]) q[++qt] = s2;
}
}
cout << endl;
}
}
#include<string.h>
void main()
{
char c[30], d[30], w[27], *c1, *d1;
int g[26][26], v[26], p[26], q[26], qh, qt, s1, s2, n;
for (; 1;)
{
cin >> c;
if (cin.fail()) break;
memset(g, 0, sizeof(g));
memset(v, 0xFF, sizeof(v));
memset(p, 0, sizeof(p));
n = 0;
if (*c == '#')
{
cout << endl;
continue;
}
for (cin >> d; *d != '#'; cin >> d)
{
for (c1 = c, d1 = d; *c1 && *d1 && *c1 == *d1; c1++, d1++);
if (*c1 && *d1)
{
if (v[*c1  'A'] == 1)
w[s1 = v[*c1  'A'] = n++] = *c1;
else
s1 = v[*c1  'A'];
if (v[*d1  'A'] == 1)
w[s2 = v[*d1  'A'] = n++] = *d1;
else
s2 = v[*d1  'A'];
g[s1][s2] = 1;
p[s2]++;
strcpy(c, d);
}
else if (!(*c1)) strcpy(c, d);
}
for (s2 = 0; p[s2]; s2++);
q[0] = s2;
for (qh = qt = 0; qh <= qt; qh++)
{
s1 = q[qh];
cout << w[s1];
for (s2 = 0; s2 < n; s2++)
if (g[s1][s2])
{
p[s2];
if (!p[s2]) q[++qt] = s2;
}
}
cout << endl;
}
}
200
It always get RE. But I don't know what's wrong with my program. Could someone help me? I think the code isn't hard for you read.
[c]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define YES 1
#define NO 0
void main(void)
{
int len1,len2,len,x,cost[26][26],in[26],y,stack[26],top,v[26];
char s1[20],s2[20],c1,c2;
for(x=0;x<26;x++)
v[x]=NO,in[x]=0;
for(x=0;x<26;x++)
for(y=0;y<26;y++)
cost[x][y]=NO;
scanf("%s",s1);
if(strcmp(s1,"#")==0)
exit(0);
while(1)
{
scanf("%s",s2);
if(strcmp(s2,"#")==0)
break;
len1=strlen(s1);
len2=strlen(s2);
if(len1<len2)
len=len1;
else
len=len2;
for(x=0;x<len;x++)
if(s1[x]!=s2[x])
break;
if(x==len)
{
strcpy(s1,s2);
continue;
}
c1=s1[x],c2=s2[x];
v[c1'A']=v[c2'A']=YES;
cost[c1'A'][c2'A']=YES;
in[c2'A']++;
strcpy(s1,s2);
}
for(x=0,top=1;x<26;x++)
if(v[x] && !in[x])
stack[++top]=x;
while(1)
{
if(top==1)
break;
x=stack[top];
for(y=0;y<26;y++)
if(v[y] && cost[x][y])
{
cost[x][y]=NO;
in[y];
if(in[y]==0)
stack[++top]=y;
}
printf("%c",'A'+x);
}
printf("\n");
}
[/c]
[c]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define YES 1
#define NO 0
void main(void)
{
int len1,len2,len,x,cost[26][26],in[26],y,stack[26],top,v[26];
char s1[20],s2[20],c1,c2;
for(x=0;x<26;x++)
v[x]=NO,in[x]=0;
for(x=0;x<26;x++)
for(y=0;y<26;y++)
cost[x][y]=NO;
scanf("%s",s1);
if(strcmp(s1,"#")==0)
exit(0);
while(1)
{
scanf("%s",s2);
if(strcmp(s2,"#")==0)
break;
len1=strlen(s1);
len2=strlen(s2);
if(len1<len2)
len=len1;
else
len=len2;
for(x=0;x<len;x++)
if(s1[x]!=s2[x])
break;
if(x==len)
{
strcpy(s1,s2);
continue;
}
c1=s1[x],c2=s2[x];
v[c1'A']=v[c2'A']=YES;
cost[c1'A'][c2'A']=YES;
in[c2'A']++;
strcpy(s1,s2);
}
for(x=0,top=1;x<26;x++)
if(v[x] && !in[x])
stack[++top]=x;
while(1)
{
if(top==1)
break;
x=stack[top];
for(y=0;y<26;y++)
if(v[y] && cost[x][y])
{
cost[x][y]=NO;
in[y];
if(in[y]==0)
stack[++top]=y;
}
printf("%c",'A'+x);
}
printf("\n");
}
[/c]
Problem 200  Runtime error(SIGSEGV)
What's runtime error mean? I think I had done it right.
Sample input
xxyy
yywz
zzw
#
/*output */
xywz
Please explain to me, what should i do?
Sample input
xxyy
yywz
zzw
#
/*output */
xywz
Please explain to me, what should i do?
Re: Problem 200  Runtime error(SIGSEGV)
[quote="Madouka"]What's runtime error mean? I think I had done it right.
Sample input
xxyy
yywz
zzw
#
/*output */
xywz
Please explain to me, what should i do?[/quote]
I think the right is xyz,not xywz as you said...
Sample input
xxyy
yywz
zzw
#
/*output */
xywz
Please explain to me, what should i do?[/quote]
I think the right is xyz,not xywz as you said...
[quote="cytse"]Well...I don't think the input data provided by Madouka is valid, because it does not provide enough information for a complete ordering.[/quote]
hmm..this is my carelessness...
the problem said :
"Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used. "
hmm..this is my carelessness...
the problem said :
"Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used. "
i just solved this problem this morning. it's easy.
take it easy and use functions. don't write everything in the main(). this is unreadable, and people can't help you.
my basic algo is:
if letter X goes before letter Y, matrix[x][Y] = 1
you then have a graph, and wish to find the longer path in it.
find the first element. easy: the first element has no ancestor in the graph.
then call a recursive function to find the successor of the first element.
i call order[X] the length of the longest path starting from X.
notice that if Yi are successors of X then order[X] = max(order[Yi]) + 1.
the successor of X is then the Yi that has the biggest order.
when this is done, just follow the list of successors from the first letter (order = N if there are N letters) to the last one (order = 0).
example:
XYZ
XZ
ZY
ZX
#
line 1 and 2 give you: Y goes before Z
line 2 and 3 give you: X goes before Z
line 3 and 4 give you: Y goes before X
the matrix is then:
+XYZ
X001
Y101
Z000
notice that Y has no successor (row of 0's), it is the first element.
then Y has two successors X and Z, find their order.
+X has one successor Z, find its order.
++Z has no successor, its order is 1
+the order of X is then 1+1 = 2 and its successor is Z
+order of Z already computed, 0.
thus order of Y = max(1,0) + 1 = 2, and its successor is X.
the order is then Y > X > Z
hope this is clear, good luck
take it easy and use functions. don't write everything in the main(). this is unreadable, and people can't help you.
my basic algo is:
if letter X goes before letter Y, matrix[x][Y] = 1
you then have a graph, and wish to find the longer path in it.
find the first element. easy: the first element has no ancestor in the graph.
then call a recursive function to find the successor of the first element.
i call order[X] the length of the longest path starting from X.
notice that if Yi are successors of X then order[X] = max(order[Yi]) + 1.
the successor of X is then the Yi that has the biggest order.
when this is done, just follow the list of successors from the first letter (order = N if there are N letters) to the last one (order = 0).
example:
XYZ
XZ
ZY
ZX
#
line 1 and 2 give you: Y goes before Z
line 2 and 3 give you: X goes before Z
line 3 and 4 give you: Y goes before X
the matrix is then:
+XYZ
X001
Y101
Z000
notice that Y has no successor (row of 0's), it is the first element.
then Y has two successors X and Z, find their order.
+X has one successor Z, find its order.
++Z has no successor, its order is 1
+the order of X is then 1+1 = 2 and its successor is Z
+order of Z already computed, 0.
thus order of Y = max(1,0) + 1 = 2, and its successor is X.
the order is then Y > X > Z
hope this is clear, good luck
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. Tomasso Toffoli
200 Problem
Hi!
I am new not only in programming but also in online contests.
here I was trying to solve 200.
I have solved few problems related with lexographic comparisons.
But this seems inverse of that?
I am not getting any clue. Help please
I am new not only in programming but also in online contests.
here I was trying to solve 200.
I have solved few problems related with lexographic comparisons.
But this seems inverse of that?
I am not getting any clue. Help please
My own quote:
We are here as Adam and Eve were here!
We are here as Adam and Eve were here!

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
Hello, I it is indeed a lexicographical comparison.
Long time ago, I solved this with crude logic that I can't even remember today. However, I then studied Topological Sort and solved it again using that algo.
From Line 1 and Line 2, we know X < Z.
From Line 2 and Line 3, we can't get any additional info.
From Line 3 and Line 4, we know Y < W.
From Line 4 and Line 5, we know Z < Y.
Based on 3 relations above, we know the output should be X < Z < Y < W.
turuthok
Long time ago, I solved this with crude logic that I can't even remember today. However, I then studied Topological Sort and solved it again using that algo.
Code: Select all
XWY
ZX
ZXY
ZXW
YWWX
From Line 2 and Line 3, we can't get any additional info.
From Line 3 and Line 4, we know Y < W.
From Line 4 and Line 5, we know Z < Y.
Based on 3 relations above, we know the output should be X < Z < Y < W.
turuthok
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
200 Rare Order [Topological Sort]
I got WA,and I still cannot find any wrong in my code.
please help me! Thanks!!
[c]#include "stdio.h"
#include "string.h"
int mark[26],map[26][26],degree[26];
void main()
{
char arr[27],lastarr[27];
int i,j,k,n,len1,len2,len;
memset(mark,0,sizeof(mark));
memset(map,0,sizeof(map));
memset(degree,0,sizeof(degree));
n=0;
while( gets(arr) ){
if(!strlen(arr)) continue;
if(arr[0]=='#') break;
if(n){
len1=strlen(lastarr);
len2=strlen(arr);
for(i=0;i<len1;i++) mark[lastarr'A']=1;
for(i=0;i<len2;i++) mark[arr'A']=1;
len=len1<len2?len1:len2;
for(i=0;i<len;i++)
if(lastarr!=arr&&map[lastarr'A'][arr'A']==0){
degree[arr'A']++;
map[lastarr'A'][arr'A']=1;
break;
}
}
n++;
strcpy(lastarr,arr);
}
do{
k=1;
for(i=0;i<26;i++){
if(degree==0&&mark[i]==1){
mark[i]=0;
for(j=0;j<26;j++)
if(map[i][j] && degree[j]>0)
degree[j];
printf("%c",i+'A');
k=0;
break;
}
}
}while(!k);
}[/c]
my method is:
please help me! Thanks!!
[c]#include "stdio.h"
#include "string.h"
int mark[26],map[26][26],degree[26];
void main()
{
char arr[27],lastarr[27];
int i,j,k,n,len1,len2,len;
memset(mark,0,sizeof(mark));
memset(map,0,sizeof(map));
memset(degree,0,sizeof(degree));
n=0;
while( gets(arr) ){
if(!strlen(arr)) continue;
if(arr[0]=='#') break;
if(n){
len1=strlen(lastarr);
len2=strlen(arr);
for(i=0;i<len1;i++) mark[lastarr'A']=1;
for(i=0;i<len2;i++) mark[arr'A']=1;
len=len1<len2?len1:len2;
for(i=0;i<len;i++)
if(lastarr!=arr&&map[lastarr'A'][arr'A']==0){
degree[arr'A']++;
map[lastarr'A'][arr'A']=1;
break;
}
}
n++;
strcpy(lastarr,arr);
}
do{
k=1;
for(i=0;i<26;i++){
if(degree==0&&mark[i]==1){
mark[i]=0;
for(j=0;j<26;j++)
if(map[i][j] && degree[j]>0)
degree[j];
printf("%c",i+'A');
k=0;
break;
}
}
}while(!k);
}[/c]
my method is:
Code: Select all
topological sort
200(Run Time Error)
Here is my coding for problem 200(Rare Order). I know it seems way too big for some of you but still I dont think it should get RTE. Can anybode tell
me where is the problem?
#include<stdio.h>
#include<string.h>
#define MAX 1000
#define SMAX 60
/* global declaration */
char ordlist[MAX];
char str[MAX][SMAX];
int l=0,num=0;
int StringCompare(char *str1,char *str2);
void replace(char c1, char c2);
int main()
{
char tmp[SMAX];
int i=0,ind=0;
while(gets(tmp)!=NULL)
{
if(!strcmp(tmp,"#")) break;
strcpy(str,tmp);
num++;
i++;
}
for(i=1;i<num;i++)
{
ind=StringCompare(str[i1],str);
if(ind<0) continue;
replace(str[i1][ind],str[ind]);
}
ordlist[l]='\0';
l=0;
printf("%s",ordlist);
return 0;
}
int StringCompare(char *str1, char *str2)/*finds the first unmatch index between str1 and str2*/
{
int i=0;
char *tmp1,*tmp2;
if(strlen(str1)>=strlen(str2))
{strcpy(tmp1,str1); strcpy(tmp2,str2);}
else
{strcpy(tmp1,str2);strcpy(tmp2,str1);}
for(i=0;i<strlen(tmp1);i++)
if(i<strlen(tmp2))
{
if(tmp1!=tmp2)
return i;
}
else
return 1;
return 1;
}
void replace(char c1,char c2)/*places c1 and c2 in ordlist according to the order c1, c2*/
{
int i,keep,ind1=1,ind2=1;
char tmp;
for(i=0;i<l;i++)/* finds the position of c1 in ordlist*/
if(ordlist==c1)
{
ind1=i; break;
}
for(i=0;i<l;i++)/* finds the position of c2 in ordlist*/
if(ordlist==c2)
{
ind2=i; break;
}
if(ind1<0 && ind2<0)/*when c1 and c2 both are not found in ordlist*/
{
ordlist[l]=c1;
ordlist[l+1]=c2;
l+=2;
return;
}
else if(ind1<0)/*when c1 not found in ordlist*/
{
for(i=(l1);i>=ind2;i)
ordlist[i+1]=ordlist;
ordlist[ind2]=c1;
l++;
}
else if(ind2<0)/*when c2 not found in ordlist*/
{
ordlist[l]=c2;
l++;
}
else
{
if(ind1>ind2)/*when both are found */
{
tmp=ordlist[ind2];
for(i=ind2+1;i<=ind1;i++)
ordlist[i1]=ordlist;
ordlist[ind1]=tmp;
}
}
}[/c]
me where is the problem?
#include<stdio.h>
#include<string.h>
#define MAX 1000
#define SMAX 60
/* global declaration */
char ordlist[MAX];
char str[MAX][SMAX];
int l=0,num=0;
int StringCompare(char *str1,char *str2);
void replace(char c1, char c2);
int main()
{
char tmp[SMAX];
int i=0,ind=0;
while(gets(tmp)!=NULL)
{
if(!strcmp(tmp,"#")) break;
strcpy(str,tmp);
num++;
i++;
}
for(i=1;i<num;i++)
{
ind=StringCompare(str[i1],str);
if(ind<0) continue;
replace(str[i1][ind],str[ind]);
}
ordlist[l]='\0';
l=0;
printf("%s",ordlist);
return 0;
}
int StringCompare(char *str1, char *str2)/*finds the first unmatch index between str1 and str2*/
{
int i=0;
char *tmp1,*tmp2;
if(strlen(str1)>=strlen(str2))
{strcpy(tmp1,str1); strcpy(tmp2,str2);}
else
{strcpy(tmp1,str2);strcpy(tmp2,str1);}
for(i=0;i<strlen(tmp1);i++)
if(i<strlen(tmp2))
{
if(tmp1!=tmp2)
return i;
}
else
return 1;
return 1;
}
void replace(char c1,char c2)/*places c1 and c2 in ordlist according to the order c1, c2*/
{
int i,keep,ind1=1,ind2=1;
char tmp;
for(i=0;i<l;i++)/* finds the position of c1 in ordlist*/
if(ordlist==c1)
{
ind1=i; break;
}
for(i=0;i<l;i++)/* finds the position of c2 in ordlist*/
if(ordlist==c2)
{
ind2=i; break;
}
if(ind1<0 && ind2<0)/*when c1 and c2 both are not found in ordlist*/
{
ordlist[l]=c1;
ordlist[l+1]=c2;
l+=2;
return;
}
else if(ind1<0)/*when c1 not found in ordlist*/
{
for(i=(l1);i>=ind2;i)
ordlist[i+1]=ordlist;
ordlist[ind2]=c1;
l++;
}
else if(ind2<0)/*when c2 not found in ordlist*/
{
ordlist[l]=c2;
l++;
}
else
{
if(ind1>ind2)/*when both are found */
{
tmp=ordlist[ind2];
for(i=ind2+1;i<=ind1;i++)
ordlist[i1]=ordlist;
ordlist[ind1]=tmp;
}
}
}[/c]
novice programmer