OJ Board

Although its fairly easy to determine valid answers on this problem, and the output specified provides the expected output format, it is also clear from the diagram that every single one of the output cases listed in the output is invalid using the diagram shown in the description.

I think for this problem, the sample output of the problem is just to give us the format of the output only, as we can deduce from the diagram that the outputs are incorrect.

How many cases are there in total?

Finially I got AC.
There are 44 possibilities.

Simply hard code it and get 0.000s

I really can't get the description. It says that the edge should be used only once, but in the sample output 12435(1-2)3. That is the question...

For this, I think you should ignore the sample output ... even the length of each output there is not right ...

-turuthok-

Can someone tell me what is wrong with my code. I am getting wrong anser but i have no clue what could be wrong. Here is my program


#include <stdio.h>
#include <malloc.h>


struct s
{
int veza[4];
};
typedef struct s cvor;


int *ProdjiTocku(int stage,int *array,int *n,int t,cvor *tocka,int *veza);
void Merge(int *array1,int *array2,int stage);
void Zamijeni(int *array,int i,int j);

int main()
{
int m,i,j,e,array[3000][10]={0},veza[5][5]={0};
int *index_array,n;
double broj1,broj2,d;
cvor tocka[5];

n=0; /* number of paths */


/* initializing */
tocka[0].veza[0]=1; /* tocka mens point on house */
tocka[0].veza[1]=2;
tocka[0].veza[2]=4;
tocka[0].veza[3]=10;

tocka[1].veza[0]=2;
tocka[1].veza[1]=4;
tocka[1].veza[2]=0;
tocka[1].veza[3]=10;

tocka[2].veza[0]=3;
tocka[2].veza[1]=4;
tocka[2].veza[2]=0;
tocka[2].veza[3]=1;

tocka[3].veza[0]=4;
tocka[3].veza[1]=2;
tocka[3].veza[2]=10;
tocka[3].veza[3]=10;

tocka[4].veza[0]=0;
tocka[4].veza[1]=1;
tocka[4].veza[2]=2;
tocka[4].veza[3]=3;
/* initializing */

index_array=ProdjiTocku(0,&array[0][0],&n,0,&tocka[0],&veza[0][0]);


/* sorting all finished paths*/


for(i=1;i<n-1;i++)
{
for(j=i;j<n;j++)
{
d=0.0001;
broj1=0;
broj2=0;
for(e=8;e>=1;e--)
{
broj1+=array[e]*d;
broj2+=array[j][e]*d;
d*=10;
}
if(broj1>broj2)
Zamijeni(&array[0][0],j,i);
}
}

m=1;

/* printing solution */
while(index_array[m]!=0)
{
for(i=1;i<=9;i++)
printf("%d",array[m]+1);
if( m < n)
printf("\n");
m++;
}
return 0;
}

int *ProdjiTocku(int stage,int *array,int *n,int t,cvor *tocka,int *veza)
{
int *ind_array,*pom;
int i;

ind_array=NULL;
pom=NULL;
stage++;

if(stage==9)
{
ind_array=(int *)malloc(3000*sizeof(int));
(*n)++;
for(i=0;i<3000;i++)
ind_array=0;
ind_array[*n]=*n;
array[(*n)*10+stage]=t;
return ind_array;
}
else
{
for(i=0;i<=3;i++)
{
if( (veza[tocka[t].veza+t*5] == 0) && (tocka[t].veza!=10) )
{
veza[t*5+tocka[t].veza] = 1; /* closing path */
veza[5*tocka[t].veza+t] = 1; /* closing path */

pom = ProdjiTocku(stage,array,n,tocka[t].veza,tocka,veza);

veza[t*5+tocka[t].veza] = 0; /* opening path */
veza[5*tocka[t].veza+t] = 0; /* opening path */

if(ind_array == NULL)
ind_array = pom;
else
{
Merge(ind_array,pom,stage); /* spaja nam ova dva polja */
free(pom);
}

}

}
if(ind_array!=NULL)
{
for(i=1;i<3000;i++)
{
if(ind_array[i])
array[i*10+stage]=t;
}
}
}
return ind_array;
}

void Merge(int *array1,int *array2,int stage)
{
int i;
if( (array2 != NULL) && (array1 != NULL) )
for(i=1;i<3000;i++)
{
if(array2[i])
array1[i]=array2[i];
}
}

/* this switches two rows */
void Zamijeni(int *array,int i,int j)
{
int k;
int pom;
for(k=1;k<=8;k++)
{
pom=array[j*10+k];
array[j*10+k]=array[i*10+k];
array[i*10+k]=pom;
}
}[c]
Outputs look OK to me but it seems I forgot something. [/c]

10153EN wrote:I think for this problem, the sample output of the problem is just to give us the format of the output only

10153EN is right.
The sample output is just a "FORMAT",not part of the anwser.
I just got AC by using DFS.

Give it a try

Cannot figure out what confs are missing..
mines are:

123153452
123154352
123453152
123543152
125315432
125431532
152345312
152354312
153123452
153125432
153254312
153452312
154312352
154312532
154325312
154352312

there are total 44 valid configurations. you have missed a lot of them. the first one you've missed in lexicographic order is
123451352
hope you'll get the others now.
thank you.

Got AC thanks..

Your output is wrong because you forgot to put in order.
Make a quick sort that you will get AC!

The correct output is:

<SPOILER REMOVED>

Hey malf....edit your post and remove the answers.

It's no fun if you allow people to just cut and paste the answers...