## 168 - Theseus and the Minotaur

All about problems in Volume 1. 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
!!!!!

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
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
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
New poster
Posts: 11
Joined: Mon Oct 29, 2001 2:00 am
Location: Bulgaria

### 168 - Theseus and the Minotaur

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
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
If you weren't lazy you would have found yourself on the ranklist!

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
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
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm
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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
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
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

elsyerra82
New poster
Posts: 4
Joined: Fri May 30, 2003 10:27 pm

### need more output samples

Hello,,

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

Thank you....

RuiFerreira
New poster
Posts: 23
Joined: Mon Dec 16, 2002 8:01 pm
Location: Portugal
Contact:

### 168 Theseus and the Minotaur

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?

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
Please visit my webpage!! I've got a lot of UVA statistics scripts
http://www.fe.up.pt/~ei01081/scripts/

RuiFerreira
New poster
Posts: 23
Joined: Mon Dec 16, 2002 8:01 pm
Location: Portugal
Contact:

### after some days...

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
Please visit my webpage!! I've got a lot of UVA statistics scripts
http://www.fe.up.pt/~ei01081/scripts/

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
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
__nOi.m....

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am