291 - The House Of Santa Claus

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

Problem 291: Problem description wrong

Post by dawynn »

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.

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN »

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.

haaaz
New poster
Posts: 29
Joined: Sun Sep 08, 2002 8:02 am

p291

Post by haaaz »

How many cases are there in total?

haaaz
New poster
Posts: 29
Joined: Sun Sep 08, 2002 8:02 am

Post by haaaz »

Finially I got AC.
There are 44 possibilities.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric »

Simply hard code it and get 0.000s

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

291 - several times read, but couldn't get the description..

Post by Dmytro Chernysh »

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

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

Post by turuthok »

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

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

dioniz69
New poster
Posts: 3
Joined: Wed Jul 23, 2003 11:45 am

291 Wrong Answer ???

Post by dioniz69 »

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]

InOutMoTo
New poster
Posts: 18
Joined: Sun Aug 10, 2003 12:47 pm

Post by InOutMoTo »

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 :lol:

Mistobaan
New poster
Posts: 2
Joined: Thu Sep 18, 2003 8:59 am
Location: Italy
Contact:

291 - The House Of Santa Claus

Post by Mistobaan »

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
Doing the things knowing that there is not best mode to do they, is awesome.

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy »

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.
Istiaque Ahmed [the LA-Z-BOy]

Mistobaan
New poster
Posts: 2
Joined: Thu Sep 18, 2003 8:59 am
Location: Italy
Contact:

Post by Mistobaan »

Got AC thanks.. 8)
Doing the things knowing that there is not best mode to do they, is awesome.

malf
New poster
Posts: 7
Joined: Tue Aug 17, 2004 5:43 pm

Post by malf »

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

malf
New poster
Posts: 7
Joined: Tue Aug 17, 2004 5:43 pm

Post by malf »

The correct output is:

<SPOILER REMOVED>

alexg
New poster
Posts: 5
Joined: Wed Sep 01, 2004 11:24 am
Location: London, UK

Post by alexg »

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

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

Post Reply

Return to “Volume 2 (200-299)”