UVa 606

From Algorithmist
Jump to navigation Jump to search

606 - Keeps Going and Going and ...[edit]

Summary[edit]

This problem is about recursions obviously, but optimization is needed.

Explanation[edit]

The bruteforce/recursive solution is easy and explicit. However, it is possible that the recursive levels are so high that we are out of computing resources (memory & time) before reaching the result. For example, knowing A=1A, calculating A[1,000,000,000] recursively would be computationally formidable.

To cut down the running time, we need to find out the repeating patterns of the lists, if there exist. Some lists do have detectable repeating patterns. Your program would get accepted as long as the following three cases are handled.

  • (1) Self recursions. e.g. A = 1A = 111...
  • (2) Mutual recursions. e.g. A = 1B, B = 2A. So A = 12A and B = 21B, which fall into case (1).
  • (3) Recursions involving 3 symbols. e.g. A = 1B, B = 2C, C = 3A. So A = 12C, B = 23A, C = 31B, which fall into case (2).

Gotchas[edit]

  • N/A

Input[edit]

1

26 26
A = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 A
B = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 B
C = 1 2 3 4 5 6 7 8 9 10 11 12 13 C
D = 1 2 3 4 5 6 7 8 9 10 11 D
E = 1 2 3 4 5 6 7 E
F = 1 2 3 4 5 F
G = 1 2 3 G
H = 1 2 H
I = zip A B
J = zip I C
K = zip J D
L = zip K E
M = zip F K
N = zip G M
O = zip H N
P = zip B E
Q = zip J N
R = 24 25 26 27 28 29 A
S = 30 31 32 T
T = 33 34 35 U
U = 36 37 38 S
V = 39 40 T
W = zip R B
X = zip S V
Y = zip Q X
Z = zip R Y
A 762436411 762436414
B 1724284849 1724284866
C 1410920471 1410920488
D 789734893 789734899
E 1303541427 1303541435
F 1354527721 1354527725
G 978569999 978570008
H 98526629 98526632
I 2081163563 2081163582
J 1434826529 1434826535
K 1019219207 1019219216
L 1390781533 1390781533
M 1975939747 1975939753
N 341649753 341649758
O 1430492671 1430492677
P 506331669 506331681
Q 491098907 491098918
R 1022995089 1022995099
S 1486898679 1486898694
T 201154253 201154260
U 25774739 25774758
V 588126921 588126940
W 1978924271 1978924285
X 676633221 676633230
Y 1437432075 1437432084
Z 1103714817 1103714826

Output[edit]

5 6 7 8
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 2
13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4
3 4 5 6 7 8 9
7 1 2 3 4 5 6 7 1
2 3 4 5 1
3 1 2 3 1 2 3 1 2 3
2 1 2 1
4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14
10 9 11 14 12 10 13
9 20 10 6 11 11 1 7 2 21
1
6 5 9 1 7 2 16
4 3 12 1 5 2
3 1 3 2 5 1 1
6 13 7 14 1 15 2 16 3 17 4 18 5
4 17 1 11 8 20 2 12 5 18 3 13
3 4 5 6 7 8 9 10 11 12 13
33 34 35 36 37 38 30 31 32 33 34 35 36 37 38 30
38 30 31 32 33 34 35 36
35 36 37 38 30 31 32 33 34 35 36 37 38 30 31 32 33 34 35 36
37 38 30 31 32 33 34 35 36 37 38 30 31 32 33 34 35 36 37 38
10 15 11 16 12 17 13 18 14 19 15 20 16 21 17
35 35 36 36 37 37 38 38 30 30
37 4 37 5 38 11 38 2 30 5
13 4 34 5 3 6 35 7 4 8