10507 - Waking up brain

[sergio]

This is my test case.

8
0
TYJ
10
20
ABC
AB
BC
CD
DE
EF
FG
IJ
FI
IC
DA
BJ
FJ
AC
DF
HI
HB
GA
GF
BG
CH
6
14
ABC
AB
AC
BC
AD
BD
CD
AE
BE
CE
DE
FB
FC
FD
FE
8
16
XYZ
ZA
AX
BY
BZ
CX
CY
DZ
YD
XE
ZE
XY
YZ
ZX
EF
CA
BD
7
12
JOM
PO
PJ
LM
PM
NO
NP
QP
QN
NM
QJ
LJ
LP
3
0
IUH
6
9
ABC
AD
BD
EC
ED
EA
FE
FA
FB
DC
6
9
ABC
AD
BD
CD
EC
ED
EA
FD
FC
FA

And my answer is:

THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 2, YEARS
THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 0, YEARS
WAKE UP IN, 3, YEARS
WAKE UP IN, 2, YEARS

S

[carneiro]

And here is the correct output for your input :

THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 2, YEARS
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 3, YEARS
WAKE UP IN, 0, YEARS
WAKE UP IN, 3, YEARS
WAKE UP IN, 2, YEARS


Notice in the 6th line, we have different outputs !! Hope this helps. Which university are you from ?

[sergio]

The 5th line is different, not the 6th

I study at Federal Universty of the Rio Grande do Norte

I was with a stupid error in the range of my loop, but now it's ok and e got accepted

Thank's a lot

[Sedefcho]

Here are several test cases ( to summarize the test
cases found here / in this thread / PLUS some more ).
The output is from an ACC program of course.

I hope they will be useful to someone.


INPUT

Code: Select all

6
11
HAB
AB
AC
AH
BD
BC
BF
CD
CF
CH
DF
FH

5 
0 
ABZ

5 
6 
ABC 
AD 
AE 
BD 
BE 
CD 
CE 

3 
0 
ABZ 

4 
0 
ATJ 

11
12
ABCD
AB
BC
CD
BE
AE
AF
AG
AH
AI
AJ
AK
KJ

8 
0 
TYJ 

10 
20 
ABC 
AB 
BC 
CD 
DE 
EF 
FG 
IJ 
FI 
IC 
DA 
BJ 
FJ 
AC 
DF 
HI 
HB 
GA 
GF 
BG 
CH 

6 
14 
ABC 
AB 
AC 
BC 
AD 
BD 
CD 
AE 
BE 
CE 
DE 
FB 
FC 
FD 
FE 

8 
16 
XYZ 
ZA 
AX 
BY 
BZ 
CX 
CY 
DZ 
YD 
XE 
ZE 
XY 
YZ 
ZX 
EF 
CA 
BD 

7 
12 
JOM 
PO 
PJ 
LM 
PM 
NO 
NP 
QP 
QN 
NM 
QJ 
LJ 
LP 

3 
0 
IUH 

6 
9 
ABC 
AD 
BD 
EC 
ED 
EA 
FE 
FA 
FB 
DC 

6 
9 
ABC 
AD 
BD 
CD 
EC 
ED 
EA 
FD 
FC 
FA

OUTPUT

Code: Select all

WAKE UP IN, 3, YEARS
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 1, YEARS
WAKE UP IN, 0, YEARS
THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 2, YEARS
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 3, YEARS
WAKE UP IN, 0, YEARS
WAKE UP IN, 3, YEARS
WAKE UP IN, 2, YEARS

Good luck to everyone!

[tryit1]

i solved this problem using simulated vertices and then if any group(graph) non simulated vertex is connected to group(graph) of simulated vertices then increment current years.
After sometime (years < 26) either all vertices are simulated or they are not , this is because the longest path in the graph is less than 26 (26 -3 or so )


how to solve this problem using union find . i don't get the idea quite.

[vsha041]

There are two tricky cases to consider:

1. Remember that all the specified areas of the brain should be awake. For example in the case below there are 5 areas. However after doing the analysis you will realize that 4 areas are awake - three already and then W. But that doesn't mean that the answer is one year. The answer here is "THE BRAIN NEVER WAKES UP" because the 5th area never wakes up. The fifth area alphabet is not even mentioned in the input data-set.

5
3
XYZ
WX
WY
WZ

Answer is "THE BRAIN NEVER WAKES UP"

2. Another case is to remember when all the areas of the brain are already awake. For example:

3
1
XYZ
XY

In this case the answer will be "WAKE UP IN, 0, YEARS"

[rcanepa]

How can this input be correct?
8
16
XYZ
ZA
AX
BY
BZ
CX
CY
DZ
YD
XE
ZE
XY
YZ
ZX
EF
CA
BD

It says 8 slept parts but the connections (letter pairs) shows that there are 9 (9 different letters) parts. What should I do with this kind of inputs? Should I work with the first 8 letters and forget about awake the rest?

[Zyaad Jaunnoo]

How can this input be correct?
8
16
XYZ
ZA
AX
BY
BZ
CX
CY
DZ
YD
XE
ZE
XY
YZ
ZX
EF
CA
BD

It says 8 slept parts but the connections (letter pairs) shows that there are 9 (9 different letters) parts. What should I do with this kind of inputs? Should I work with the first 8 letters and forget about awake the rest?

It is not correct as it has 9 different letters and N = 8.

[lnr]

Deleted after getting Accepted.

[kowsercse]

I am confused with the sample input given in the problem. Can you please explain me the input. What does 6 in the first line refers to? What are the slept areas initially? There are only 6 areas mentioned: A, B, C, D, F and H. What about remaining 5 areas.

Code: Select all

6
11
HAB
AB
AC
AH
BD
BC
BF
CD
CF
CH
DF
FH