## 10507 - Waking up brain

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

Moderator: Board moderators

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

### 10507 - Waking up brain

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?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland
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.

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China
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.

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
I got the same problem ...

But my question is to kuegel

How do you get to know ALL mistakes so soon ?
[]s
Mauricio Oliveira Carneiro

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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.

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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
[]s
Mauricio Oliveira Carneiro

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland
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

``````

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
and does it skip lines for each output ?
[]s
Mauricio Oliveira Carneiro

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
argh, accepted .
I can't believe the problem was that I was not "reseting" the graph for each input

duhhhh

ok, thanls everyone.
[]s
Mauricio Oliveira Carneiro

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:
Hi,

I tried to solve this problem, but I only get WA

So, anyone can to put other test cases?

S

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
Have you tried the input cases here in the forum ?
[]s
Mauricio Oliveira Carneiro

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:
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

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
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.
[]s
Mauricio Oliveira Carneiro