どきどきトロッコ 横へな2016.7.2 問題

問題の概要

あなたはトロッコに乗っています。
目の前には分かれ道が！
生き残るためにはどの道に行けばよいでしょうか？

詳細

1	2	3
4	5	6
7	8	9

(a), (b), (c) の3つの道をえらぶことが出来ます。無事に ゴールまでたどり着けるのがどの選択肢なのかを答えて下さい。
行く手には、右図の 1番から9番にあるようなコースが並んでいます。7, 8, 9 のコースにある ☓ に到達すると死亡です。
1〜6 のコースには、分岐が二箇所ずつあります。分岐に到達した場合、好きな方に行くことが出来ます。
例えば。3番のコースに上段から入った場合、上段または下段へ行くことが出来ますが、中段には行くことができません。 3番のコースに中段から入った場合、上段または中段へ行くことが出来ますが、下段には行くことができません。

入力

入力は
1728398
こんな感じ。コースの番号が左から順に区切り文字なしで並んでいます。

出力

出力は、a, b, c のうち、ゴールにたどり着ける可能性があるものを区切り文字なしで昇順に。
bc
こんな感じ。
a, b, c のどれを選んでも死を免れられない場合は - を。

補足

• 不正な入力に対処する必要はありません。
• 実装ができた方は Qiitaの記事 のコメント欄からリンクを張っていただくと見つけやすくて助かります。
• トロッコは坂道をくだっています。引き返すことはできません。
• この問題は2016年7月2日に開催される オフラインリアルタイムどう書くE05 の問題です。イベントについては Doorkeeper のページ の方を御覧下さい。

サンプルデータ

#	入力	期待	状況
0	1728398	bc
1	789	-
2	274	ac
3	185	abc
4	396	ab
5	1278	abc
6	7659832	a
7	178	bc
8	189	ab
9	197	a
10	278	ac
11	289	bc
12	297	a
13	378	ac
14	389	b
15	397	ab
16	478	c
17	489	bc
18	497	ab
19	578	bc
20	589	b
21	597	ac
22	678	c
23	689	ab
24	697	ac
25	899	b
26	7172	ac
27	54787	bc
28	83713	bc
29	149978	-
30	159735	abc
31	1449467	abc
32	9862916	b
33	96112873	ab
34	311536789	-
35	281787212994	abc
36	697535114542	ac

C/C++/Java 用のテストデータ