回答編集履歴
1
追記
test
CHANGED
@@ -35,3 +35,31 @@
|
|
35
35
|
S1, S2 の2つの文字列があたえられたときに、
|
36
36
|
|
37
37
|
S1 に何回の操作をしたら S2 になるか、あるいは何回操作しても S2 にならないかをなるべく速く判定するプログラムを書くことは可能でしょうか?
|
38
|
+
|
39
|
+
|
40
|
+
|
41
|
+
追記: 2016-04-27
|
42
|
+
|
43
|
+
N = 3 の場合の文字列の変化は次パターンがあります。
|
44
|
+
|
45
|
+
(操作をしても変化をしなくなる部分は *xxx のように書いています)
|
46
|
+
|
47
|
+
[*123]
|
48
|
+
|
49
|
+
[*132]
|
50
|
+
|
51
|
+
[213, *123]
|
52
|
+
|
53
|
+
[321, 213, *123]
|
54
|
+
|
55
|
+
[312, *123]
|
56
|
+
|
57
|
+
つまり、M >= 3 なら S の値によらず、結果は常に 123 となります。
|
58
|
+
|
59
|
+
また、 213 -> 132 へ変換されることは無いということです。
|
60
|
+
|
61
|
+
N = 3 の場合、一番長い変換シーケンスは [321, 213, *123] です。
|
62
|
+
|
63
|
+
他の N について、一番長い変換シーケンスを求めるプログラムを書くことは可能でしょうか?
|
64
|
+
|
65
|
+
|