511 - Do You Know the Way to San Jose? - Do nothing AC

The forum to report every bug you find or tell us what you'd like to find in UVa OJ

Moderator: Board moderators

Shiori
New poster
Posts: 1
Joined: Wed May 08, 2002 6:26 am

P200 : What's wrong with my program ?

Post by Shiori » Wed May 08, 2002 6:27 am

#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;
}
}

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

200

Post by htl » Tue Jul 16, 2002 6:08 pm

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]

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Mon Jul 22, 2002 5:31 pm

Could someone help me? I want to know if my code of topology sort algo is correct.

Madouka
New poster
Posts: 1
Joined: Tue Aug 06, 2002 9:57 am

Problem 200 - Runtime error(SIGSEGV)

Post by Madouka » Tue Aug 06, 2002 10:05 am

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?

pendryko
New poster
Posts: 3
Joined: Tue Oct 08, 2002 7:10 am

Post by pendryko » Wed Oct 09, 2002 4:21 am

xwy
xty
Bus error(core dumped)

i can't finish my input, because your prog is dumped.

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

Re: Problem 200 - Runtime error(SIGSEGV)

Post by supermin » Wed Oct 30, 2002 8:49 am

[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...

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Wed Oct 30, 2002 4:07 pm

Well...I don't think the input data provided by Madouka is valid, because it does not provide enough information for a complete ordering.

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

Post by supermin » Wed Oct 30, 2002 5:09 pm

[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. "

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Thu Jan 30, 2003 9:44 am

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
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Eva
New poster
Posts: 14
Joined: Thu Apr 10, 2003 11:31 am
Location: Bombay
Contact:

200 Problem

Post by Eva » Thu Apr 10, 2003 9:13 pm

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 :oops:
My own quote:

We are here as Adam and Eve were here!

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu Apr 10, 2003 11:37 pm

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.

Code: Select all

XWY
ZX
ZXY
ZXW
YWWX
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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

200 Rare Order [Topological Sort]

Post by hank » Sat Jul 26, 2003 6:52 am

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:

Code: Select all

topological sort

samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

200(Run Time Error)

Post by samueljj » Fri Aug 08, 2003 6:12 am

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[i-1],str);
if(ind<0) continue;
replace(str[i-1][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=(l-1);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[i-1]=ordlist;
ordlist[ind1]=tmp;
}
}
}[/c]
novice programmer

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri Aug 08, 2003 6:20 am

Your problem code lies in stringCompare() within the following lines:
[c]char *tmp1,*tmp2;
if(strlen(str1)>=strlen(str2))
{strcpy(tmp1,str1); strcpy(tmp2,str2);}
else
{strcpy(tmp1,str2);strcpy(tmp2,str1);}[/c]
The rest is up to you to figure out =)

samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

Post by samueljj » Sat Aug 09, 2003 6:09 am

Thanks! I got ACC now :D
novice programmer

Locked

Return to “Bugs and suggestions”