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

[bharatj]

Hi, can anyone please explain to me what this problem . Is this an ordering among characters from the strings given in the input ?
Are all string in input in order ? i.e. does WYX implies that Y comes after W and tht X comes after Y ?
If answers to both my questions is yes, then i think there can be many possible outputs but this problem doesn't seem to have a special correction program.
moreover i tried a program assuming wht i asked is true but got a WA . so i think i haven't got what the problem asks.
Can ppl who have done this prob help me out int his matter ?

[topu]

please see the code below why there shows the presentation error?


#include<stdio.h>
#include<string.h>
struct line{
char chap[20];
struct line *prev;
struct line *next;
};
struct order{
char ch;
struct order *prev;
struct order *next;
};
void main()
{
struct line *l,*temp,*base;
struct order *r,*b_r,*temp1,*temp2,*f;
char s[20],t1[20],t2[20],x;
int i,flag,flag1,flag2,n;
l=new struct line;
r=new struct order;
r->next=NULL;
r->prev=NULL;
l->next=NULL;
l->prev=NULL;
b_r=r;
base=l;
gets(s);
while(strcmp(s,"#"))
{
temp=l;
strcpy(temp->chap,s);
gets(s);
temp->next=new struct line;
l=l->next;
l->prev=temp;
l->next=NULL;
}
l=l->prev;
l->next=NULL;
temp=base;
while(temp!=NULL)
{
strcpy(t1,temp->chap);
if(t1[0]!=x)
{
r->ch=t1[0];
r->next=new struct order;
temp1=r;
r=r->next;
r->prev=temp1;
}
temp=temp->next;
x=t1[0];
}
r=r->prev;
r->next=NULL;
temp=base;
while(temp!=NULL)
{
i=1;
r=b_r;
flag=0;
flag1=0;
flag2=0;
strcpy(t1,temp->chap);
if(t1[0]==t2[0])
{
while(t1==t2)
i++;
n=strlen(t2);
if(i==n)
{
temp=temp->next;
strcpy(t2,t1);
continue;
}
while(1)
{
if(r->ch==t2)
{
flag=1;
f=r;
}
if(r->ch==t1)
{
flag1=1;
f=r;
if(flag==0)
{
temp1=new struct order;
temp1->ch=t2;
temp1->next=r;
r=r->prev;
r->next=temp1;
temp2=temp1;
temp1=temp1->next;
temp1->prev=temp2;
do
{
f=f->next;
if(f->ch==t2)
{
flag2=1;
break;
}
}while(f->next!=NULL);
if(flag2)
{
if(f->next==NULL)
{
f=f->prev;
f->next=NULL;
}
else
{
temp2=f->next;
f=f->prev;
temp1=f;
f->next=temp2;
f=f->next;
f->prev=temp1;
}
}
}
break;
}
if(r->next==NULL)
{
break;
}
r=r->next;
}
if(flag&!flag1)
{
if(f->next==NULL)
{
f->next=new struct order;
temp1=f;
f=f->next;
f->ch=t1;
f->prev=temp1;
f->next-NULL;
}
else
{
temp1=f;
temp2=new struct order;
temp2->ch=t1;
temp2->prev=f;
temp2->next=f->next;
f=f->next;
f->prev=temp2;
temp1->next=temp2;
}
}
}
temp=temp->next;
strcpy(t2,t1);
}
r=b_r;
do
{
printf("%c",r->ch);
r=r->next;
}while(r!=NULL);
delete base;
delete b_r;
delete temp2;
delete temp;
}

[Dani Rodrigo]

Code: Select all

while(i<l && s[i]==old[i]) i++; //<<-- problematic line! 
a[ old[i]-'A' ][ s[i]-'A' ] = 1; 

If you exit the while because i=l; then old or s has the value '\0'.
When you try to access to a[ old-'A' ][ s-'A' ] you get RE.
In the second code you verify that old!='\0' and s!='\0'

[topu]

the matter is , here the input is a sorted index (just as a sorted name data base).but the problem is in this case though it used the englich character the order is not the same. that mean it is not in this order (a,b,c,d.............,y,z). it is an unfamiliar language and you dont know the order. so you make the order which letter come after which from that sorted index.
may be i am clear to you.

[KS78]

The sample input is not consistant.

XWY <---- Y comes after X
ZX
ZXY
ZXW
YWWX <--- X comes after Y
#

So the order is ZXYW and not XZYW as shown in the sample output. Can someone clarify?

[topu]

you should clear the sorting of string at first. if the some name is like this (according to english character order list ) bipu,adam , amin , dip , then the sorting is like this adam,amin,bipu,dip . at first thinking about the first character. if two has the same first character then think about the two's 2nd character and that which is higher order that come first.
here the list is like this
xwy
zx
zxy
zxw
ywwx

as the first topic is startint with x and the second is with z so x comse first in the order list then z. ther is no relation with first ones "w" and second one "z" as they are sorted already with the basis of first character. when come the 3 input with same first character "z" then the matter is 2nd character here all are x so no order basis can be made. then think about the 3rd character. in zxy and zxw the zxy comes first that indicate that y comes befor w. and zxw comes before ywwwx so the z comes before y.
so at last the order is like this xzyw.
may be i am clear at this time. if not i am really sorry. wait another one may be clear you.

[Genxcop]

04765610_24.java:4: Public class `hw1' must be defined in a file called
`hw1.java'.
public class hw1
^
1 error

04765620_24.java:4: Public class `main' must be defined in a file called
`main.java'.
public class main
^
1 error


i don't know wat's wrong. It compiles on my computer fine. hw1.java was the first filename and main.java was the 2nd filename already... i don't know wat's going on.

Any ideas? Thanks in advance!

[willtio]

Ah the Java support for the online judge is bad if u read the HowTo Submit using Java link on the website...

You should not declare public class for Java.

I did mine in java and now I am using C.

=)

PS: Are you one of the COMP3121 student? =D

[richardfu71]

haha~ COMP2121....
I just start write sth in java... but i i think i should change to C...

[hazhir]

Hi
I got WA for my solution and code for rare order.
plz help me if you can.
here is my code:

Code: Select all

#include <stdio.h>
#include <conio.h>
#define offset 64

int main()
{
	char graph[27][27] = {0};	
	int exist[27] = {0};
	int count = 0;
	char *last = "";
	char *current = new char[21];	

	int flag = 0;
	while(gets(current),current[0] != '#')
	{			
		int k = 0;
		while(current[k])
		{								
			if(!exist[current[k] - offset])
				exist[current[k] - offset] = 1;
			k++;
		}

		k = 0;						
		while(last[k] && current[k])
		{
			if(last[k] != current[k])
			{
				count = graph[last[k] - offset][0];
				flag = 0;
				for(int i = 1;i<= count;i++)
					if(graph[last[k] - offset][i] == current[k])
					{
						flag = 1;
						break;
					}
				if(!flag)
				{
					graph[last[k] - offset][0]++;
					graph[last[k] - offset][graph[last[k] - offset][0]] = current[k];
				}
				break;
			}
			else
				k++;
		}							

		last = current;		
		current = new char[21];
	}

	//DFS and TOPOLOGICAL SORT
	int f[27] = {0};
	int d[27] = {0};
	int color[27] = {0};
	int stack[27] = {0};
	int counter[27];
	for(int i = 1;i<= 26;i++)
		counter[i] = 1;
	int sPoint = 0;
	int time = 0;
	int k;
	for(int i = 1;i <= 26;i++)
	{
		if(exist[i] == 1)
		{
			k = i;
			if(color[k] == 0)
			{
				do{
					if(color[k] == 0)
					{
						color[k] = 1;
						time++;
						d[k] = time;
			   			stack[sPoint] = k;
						sPoint++;
					}
					if(counter[k] <= graph[k][0] && color[graph[k][counter[k]] - offset] == 0)
					{	
						counter[k]++;						
						k = graph[k][counter[k]-1] - offset;						
					}
					else if(sPoint)
					{
						sPoint--;
						k = stack[sPoint];
						color[k] = 2;
						time++;
						f[k] = time;
					}
				}while(sPoint);
			}
		}
	}
	
	k = 0;
	int result[27];
	char letter[27];
	for(int i = 1;i <= 26;i++)
	{
		if(exist[i] == 1)
		{
			result[k] = f[i];
			letter[k] = i + offset;
			k++;
		}
	}

	int max = 0;
	int maxindex;
	for(int i = 0;i<=k-2; i++)
	{
		max = result[i];
		maxindex = i;
		for(int j = i+1;j<=k-1;j++)
		{
			if(result[j] > max)
			{
				max = result[j];
				maxindex = j;
			}
		}
		char temp = letter[maxindex];
		letter[maxindex] = letter[i];
		letter[i] = temp;

		result[maxindex] = result[i];
		result[i] = max;
	}

	for(int i = 0;i<=k-1;i++)
		printf("%c",letter[i]);
	printf("\n");
	getch();
	return 0;
}

[Jan]

Search the board first. Don't open a new thread if there is one already.

[vencentd]

help ,i do not konw what is wrong.

Code: Select all

#include<stdio.h>
#include<string.h>
int main(void){
	char array[2000][25];
	int i,k,j,min,max,count;
	int matrix[127][127];
	i=0;
	memset(array[i],'\0',21);
	while(fgets(array[i],21,stdin)){
		array[i][strlen(array[i])-1]='\0';
	/*	if(strcmp(array[i],"#")==0){*/
		if(array[i][0]=='#'){
			break;
		}
/*		printf("array=%s  %i\n",array[i],strlen(array[i]));*/

		i++;
		memset(array[i],'\0',21);
	}
	j=0;
	min=200;
	max=-1;
	for(k=0;k<i;k++){
		j=0;
		while(array[k][j]==array[k+1][j]){
			if(array[k][j]<min){
				min=array[k][j];
			}
			if(array[k+1][j]<min){
				min=array[k+1][j];
			}
			if(array[k][j]>max){
				max=array[k][j];
			}
			if(array[k+1][j]>max){
				max=array[k+1][j];
			}
			j++;
		}
/*		printf("len=%i  j=%i",strlen(array[k]),j);
		printf("k,j=%i  k+1,j=%i\n",array[k][j],array[k+1][j]);*/
		if(j==strlen(array[k])&&array[k][j-1]==array[k+1][j-1]){
                	continue;
                }

	/*	printf ("1\n");*/
		matrix[(int)array[k][j]][(int)array[k+1][j]]=1;
	}
/*	printf("min=%i=%c   max=%i=%c  \n",min,(char)min,max,(char)max);*/
	for(j=min-1;j<max+1;j++){
		for(k=min-1;k<max+1;k++){
			count=0;
			if(matrix[k][0]==7){
				continue;
			}
			for(i=min-1;i<max+1;i++){
		/*		printf("kkk%i  ",matrix[i][k]);*/
				if(matrix[i][k]==1){
					count++;
				}	
			}
		/*	printf("matrix[%i][%i]=%i  count=%i\n",i,k,matrix[i][k],count);*/
			if(count==0){
				printf("%c",k);
				for(count=0;count<max+1;count++){
					matrix[k][count]=7;
				}
		/*		printf("%i     %i\n",matrix[k][0],matrix[k][1]);*/
				break;	
			}
		}
	}
	printf("\n");
	return 0;
}

[sohel]

Search the board first before posting. Don't create a new thread for a problem if one already exists!

[vencentd]

i also get the running error ,and the code work well in my test case!can someone give me some test case ,or point out where is the bug in my code.

Code: Select all

#include<stdio.h>
#include<string.h>
int main(void){
	char array[2000][100];
	int i,k,j,min,max,count;
	int matrix[300][300];
	i=0;
	while(fgets(array[i],100,stdin)){
		array[i][strlen(array[i])-1]='\0';
		if(array[i][0]=='#'){
			i--;
			break;
		}
		i++;
		memset(array[i],'\0',21);
	}
	if(i==0){
		printf("%c",array[0][0]);
	}
	j=0;
	min=126;
	max=1;
	for(k=0;k<i;k++){
		j=0;
		while(1){
			if(array[k][j]<min){
				min=array[k][j];
			}
			if(array[k+1][j]<min){
				min=array[k+1][j];
			}
			if(array[k][j]>max){
				max=array[k][j];
			}
			if(array[k+1][j]>max){
				max=array[k+1][j];
			}
			if(array[k][j]!=array[k+1][j]){
				break;
			}
			j++;
		}
		if(j==strlen(array[k])&&array[k][j-1]==array[k+1][j-1]){
                	continue;
                }
		matrix[(int)array[k][j]][(int)array[k+1][j]]=1;
		matrix[(int)array[k][j]][0]=8;
		matrix[(int)array[k+1][j]][0]=8;
	}
	for(j=min;j<max+1;j++){
		for(k=min;k<max+1;k++){
			count=0;
			if(matrix[k][0]!=8){
				continue;
			}
			for(i=min-1;i<max+1;i++){
				if(matrix[i][k]==1){
					count++;
				}	
			}
			if(count==0){
				printf("%c",k);
				for(count=0;count<max+1;count++){
					matrix[k][count]=7;
				}
				break;	
			}
		}
	}
	printf("\n");
	return 0;
}

[ckclark]

I think the test data has some problem.
I didn't print anything and got an AC.
Please take a look on this.