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

bharatj
New poster
Posts: 3
Joined: Sun Jan 15, 2006 8:38 am

can't understand 200 - Rare Order

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
New poster
Posts: 3
Joined: Mon Nov 21, 2005 6:30 pm
Contact:

proble-200,rare-order - why presentation error?

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
New poster
Posts: 11
Joined: Sun Jul 18, 2004 1:39 am

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
New poster
Posts: 3
Joined: Mon Nov 21, 2005 6:30 pm
Contact:

rare order

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
New poster
Posts: 1
Joined: Wed Mar 15, 2006 1:44 pm

Rare Order

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
New poster
Posts: 3
Joined: Mon Nov 21, 2005 6:30 pm
Contact:
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
New poster
Posts: 3
Joined: Wed Jul 26, 2006 3:58 pm

200 - Compile Error

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.

willtio
New poster
Posts: 1
Joined: Thu Jul 27, 2006 10:53 am
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
New poster
Posts: 1
Joined: Sun Jul 30, 2006 7:03 am
haha~ COMP2121....
I just start write sth in java... but i i think i should change to C...
hazhir
New poster
Posts: 2
Joined: Fri Apr 11, 2008 7:33 pm

200- WA for rare order

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Re: 200- WA for rare order

Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage
vencentd
New poster
Posts: 3
Joined: Sun May 25, 2008 6:23 pm

help !!200 running time error

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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: help !!200 running time error

Search the board first before posting. Don't create a new thread for a problem if one already exists!
vencentd
New poster
Posts: 3
Joined: Sun May 25, 2008 6:23 pm

Re: 200(Run Time Error)

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
New poster
Posts: 5
Joined: Fri Jan 05, 2007 10:34 pm
Location: Taiwan

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

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