168 - Theseus and the Minotaur

[dawynn]

!!!!!

This would again be a case of invalid data. Actually, continuing that thought, it might look something more like this:

A:B:C:D;

And I'm assuming that we are interpreting this as, there is a pathway from A to B, and a pathway from C to D, but no pathway from B to C.

Or would A:B:C; mean that there is a pathway from A to B, and also a pathway from B to C?

Basically -- is it a typo, or is it an intentional devious trick?

[Mart]

I'm not certain of my tests (I might double check later if I have time) but I think that there are cases of the form A:B:C:E; as you suggest.

Making this A:B;C:E; doesn't work. A:BCE; also doesn't work (note - I'm assuming that the rest of my program is basically ok as it was previously accepted. Maybe a mistake...). So could it mean: A:BCE;B:CE;C:E; ? or A:B; B:C; C:E; ?

I can't see how it can be too weird, because of the previous solutions that have worked (all 12 of them... (!)). One of the solutions might have been submitted after the input data changed, but the writer of that one doesn't seem inclined to give us any input here...

Mart.

[Orgi]

I haven't got AC yet... did someone make any progress?..
there is really something wrong with the test data;
I also found that there is something like ...A:BC:D... which is incosistent with the statement
the value of k is never 0 and is not very big (shorter than 9 digits)

[dawynn]

I received one direct e-mail saying that there was a student that was supposed to be looking at it. But as yet, (s)he hadn't reported back. They've recognized that there is an issue, but the person assigned to it has not had much progress yet.

David

[dawynn]

OK, here's the kicker -- I see some people have actually been accepted recently. Anyone want to share any secrets on what assumptions need to be made? Maybe what corrections need to be made to the problem description?

[Ivor]

If you weren't lazy you would have found yourself on the ranklist!

Ivor

[dawynn]

So, documented bad problem description = my laziness? No, that doesn't seem right. Documented bad input data = my laziness? Hmm, that doesn't seem right either.

[Ivor]

The only Wynn I found in user database was David Wynn... I assumed that it's you. If so -- you have solved this problem with time 2.980s/444Kb. Rank 80. See yourself. If it's not you then my apologies.

Ivor

[dawynn]

I apologize. I misinterpreted your earlier message. Thank you for pointing that out to me. I'm assuming then that
a) They corrected the data and
b) Did a rejudgment without communictating with us.
(Normally when a rejudgment occurs and it changes the result of a submission, we receive email communication about the changed result. That never occurred for me.)

[Ivor]

Well I noticed that some replys tend to get lost from time to time. But I remeber I did receive a message about a this rejudgement.

Ivor

[elsyerra82]

Hello,,

Can I get more out put samples from acm 682......??????


Thank you....

[RuiFerreira]

Hi,

I'm having problems with this problem (more than one)

I know that there are many threads about this, and i've read the all... but they are from 2002... and I think they corrected the problem after that...

so... I have some questions...

can the k in the input be 0 ?

is this correct?
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1

out:
A B D G E F /H

are there any tricks?

my program suports caves without any conections.. like

A;B:A. or A:;B:A. or B:A,A:. or B:A,A.

I really don't know what else to test...

thanks

[RuiFerreira]

after some days with no reply...
here is my source code,

hope you can find the bug...


[c]
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 30

int grafo[MAX][MAX];
int candle[MAX];
char linha[1000],*in;

int main(void)
{
char ini;
char t,m;
int count,ct;
int flag,i;

while(1)
{
memset(grafo,0,sizeof(grafo));
gets(linha);
if (linha[0]=='#')
break;
in=linha;
while(1)
{
while(isspace(*in)) in++;
ini=*in-'A';
in++;
while(isspace(*in)) in++;
if (*in==';') { in++; continue;}
if (*in=='.') { in++; break;}
in++;
while(isspace(*in)) in++;
while(*in!=';' && *in!='.')
{
grafo[(int)ini][(int)(*in-'A')]=1;
in++;
while(isspace(*in)) in++;
}
if (*in=='.')
{
in++;
while(isspace(*in)) in++;
break;
}
in++;
while(isspace(*in)) in++;
}
sscanf(in," %c %c %d",&m,&t,&count);
m-='A';
t-='A';
ct=-1;
memset(candle,0,sizeof(candle));
while(1)
{
ct++;
if (ct==count)
{
printf("%c ",t+'A');

candle[(int)t]=1;
ct=0;
}
flag=0;
for (i=0;i<MAX;i++)
if (i!=t && grafo[(int)m] && !candle)
{
flag=1;
t=m;
m=i;
break;
}
if (!flag)
break;
}
printf("/%c\n",m+'A');
}


return 0;
}
[/c]

thanks

[Noim]

HI , RuiFerreira,

There is no test case such k=0;
and your outpur for your input mentioned earliar is same as my Accpeted code's output.


PS: i like your web site to compare two user . It's really nice

[Noim]

oh i forgot to say other things.

The initaial position of two people is adjecent of all the input data. ( i don't know if they are in same initial position or not. but i consider that case in my code. )