168 - Theseus and the Minotaur

[brianfry713]

uvatoolkit.com

[jaracz]

I gathered inputs from other posts and added mine:

Code: Select all

A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 1
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 6
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 7
A:B;B:A. B A 3
A:B;B:C;C:A. B A 6
C:A;A:B. A C 999999999
B:A;A:B. A C 999999999
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1
A:DBC. A B 20
A:DBC. A B 1
A:BC;B:CA;C:AB. A B 999999999
A:B;B:C;C:D;D:BA. A D 999999997
A:B;B:C;C:D;D:BA. A D 999999998
A:B;B:C;C:D;D:BA. A D 999999999
A:B;B:C;C:D;D:BA. A D 1000000000
#

My Java program gives immediately correct answers (compared with uvatoolkit):

Code: Select all

D F G /E
A B C D G E F /H
C D /B
A B D /C
/B
A /C
/B
/B
D F G /E
A B D G E F /H
/D
A /D
B /C
D /C
B /A
C /B
D /C

but somehow i'm getting TLE or WA (2,944) it depends on execution time.
Can someone post some tricky input for that problem ?

[LlatzerandToni]

I tried all the inputs here posted (same outputs) but I keep getting WA.

Input:

Code: Select all

A:BCD;B:ACD;C:ABD;D:ABC. A B 5
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD;Z. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD;Z:. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:ADZ;Z. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:ADZ;Z:. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:ADZ. A C 3
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 1
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 6
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 7
A:B;B:A. B A 3
A:B;B:C;C:A. B A 6
C:A;A:B. A C 999999999
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1
A:DBC;B. A B 20
A:DBC;B. A B 1
A:BC;B. A B 1
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1 
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1001
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1002
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1004
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1007
B:A;A:B;C. A C 999999999
A:BCD;B:AD;C;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
A:BCD;B:AD;C;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1
A:BC;B:CA;C:AB. A B 9
A:B;B:C;C:D;D:BA. A D 7
A:B;B:C;C:D;D:BA. A D 8
A:B;B:C;C:D;D:BA. A D 9
A:B;B:C;C:D;D:BA. A D 10
A:B;B:C;C:D;D:E;E:F;F:G;G:H;H:I;I:J;J:K;K:L;L:M;M:N;N:O;O:P;P:Q;Q:R;R:S;S:T;T:U;U:V;V:W;W:X;X:Y;Y:ABCDEFGHIJKLMNOPQRSTUVWXZ;Z:ABCDEFGHIJKLMNOPQRSTUVWXYABCDEFGHIJK. B A 1000
A:;B;C:D;D:EGH;Z:;Y. D C 1
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1000000000
A:BC;B:CA;C:AB. A B 999999999
A:B;B:C;C:D;D:BA. A D 999999997
A:B;B:C;C:D;D:BA. A D 999999998
A:B;B:C;C:D;D:BA. A D 999999999
A:B;B:C;C:D;D:BA. A D 1000000000
A:B;Z:E. A C 1
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 600
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 599
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 598
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 597
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 1
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 2
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 3
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 4
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 5
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 6
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 7
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 8
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 9
A:BC;C:E;F:A;B:D;D:EF;E:DF. A F 10
#

Output:

Code: Select all

C A /B
D F G /E
D F G /E
D F G /E
D F G /E
D F G /E
D F G /E
A B C D G E F /H
C D /B
A B D /C
/B
A /C
/B
D F G /E
A B D G E F /H
/D
A /D
A /C
A B D G E F /H
E B /H
F A /B
E D /C
E C B /H
/B
D F G /E
A B D G E F /H
B /C
D /C
B /A
C /B
D /C
A Q /P
D /E
H /F
B /C
D /C
B /A
C /B
D /C
A /B
F /E
E B /C
D /B
B D F /E
A B D E /F
B E A /C
D A /B
E D /B
F /E
A /F
B D C /A
D /B
E F /D
F /E

Any idea? Thanks in advance.

[brianfry713]

Post your code.

[LlatzerandToni]

ACed

The error was dealing with passages returing to he origin cave. For example:
Input:

Code: Select all

A:B;B:C;C:C. B A 1
#

Output:

Code: Select all

B C /C

Another hint. Don't worry about loops, I submitted a program that doesn't care about them and I didn't get TLE. Cases like:

Code: Select all

A:B;B:C;C:D;D:BA. A D 999999999

Cheers.