Page 1 of 2
10507 - Waking up brain
Posted: Mon Jun 16, 2003 2:22 pm
by szymcio2001
It seems to be an easy problem, but I steel get Wrong Answer. I simply use BFS, but I add the vertex to queue only if it is connected with three vericies I visited earlier. If the BFS doesn't visit all areas I output "THIS BRAIN NEVER..." otherwise I output the time that is needed to wake up the brain. Is this algorithm wrong or is there some tricky input? And if some edge is given in input more than once should I ignore each another or use all of them?
Posted: Mon Jun 16, 2003 8:33 pm
by Adrian Kuegel
First you should know that there are several test cases, even if the description doesn't say so. And there are inputs where the number of used letters for connections is smaller than n, like:
5
0
ABZ
Output: THIS BRAIN NEVER WAKES UP
Posted: Mon Jun 16, 2003 9:22 pm
by szymcio2001
Adrian Kuegel wrote:First you should know that there are several test cases, even if the description doesn't say so.
Thanks, my algorithm was correct but I did't consider that there could be more than one test case in the input. Now I got Acc.
Posted: Tue Jun 17, 2003 4:48 pm
by hujialie
It's really a strange problem,why does't it tell us there is multiple input?
I got wrong answer 4 times until I saw the last post.
Posted: Wed Jun 18, 2003 1:12 am
by carneiro
I got the same problem ...
But my question is to kuegel
How do you get to know ALL mistakes so soon ?
Posted: Wed Jun 18, 2003 1:17 am
by Adrian Kuegel
I don't know them soon. See the contest ranklist, I did a lot of submissions on problem A and H (H is 10507). I was almost sure my program for A was correct, so I began to check the input throwing a runtime error if something isn't correct.
Posted: Wed Jun 18, 2003 1:32 am
by carneiro
Kuegel, what should be the answer for this input ?
6
11
HAB
AB
AC
AH
BD
BC
BF
CD
CF
CH
DF
FH
3
0
ABZ
4
0
ATJ
5
0
ABZ
Posted: Wed Jun 18, 2003 1:44 am
by szymcio2001
My finally accepted program gives:
Code: Select all
WAKE UP IN, 3, YEARS
WAKE UP IN, 0, YEARS
THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
Posted: Wed Jun 18, 2003 1:48 am
by carneiro
and does it skip lines for each output ?
Posted: Wed Jun 18, 2003 7:47 am
by Dominik Michniewski
Thanks Adrian, I got Acc too ... in contest appears message that problem A has more than one inputs in file, but nothing was posted about H ...
Finally I got one more input, on which my program fails:
5
6
ABC
AD
AE
BD
BE
CD
CE
WAKE UP IN, 1, YEARS
Best regards
DM
Posted: Wed Jun 18, 2003 6:59 pm
by carneiro
argh, accepted .
I can't believe the problem was that I was not "reseting" the graph for each input
duhhhh
ok, thanls everyone.
Posted: Sun Jun 22, 2003 11:33 pm
by sergio
Hi,
I tried to solve this problem, but I only get WA
So, anyone can to put other test cases?
S
Posted: Sun Jun 22, 2003 11:57 pm
by carneiro
Have you tried the input cases here in the forum ?
Posted: Mon Jun 23, 2003 12:13 am
by sergio
Yes, I have tried all input cases in the forum and I got the corret outputs.
All outputs in the forum are corret, aren't they??
S
Posted: Mon Jun 23, 2003 12:58 am
by carneiro
yes, they are. At least the ones I posted.
Make you a huge test case, and post it in the forum, I can use my accepted program to give you the right output.