C - Brute-force Attack 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

あなたはスーパーハッカーです。高橋君を攻撃対象に定めたあなたは、
高橋君のパソコンのパスワードに関して次の事実を突き止めました。

  • 長さは N 文字である。
  • a, b, c 以外の文字は含まれない。
高橋君のパソコンのパスワードの候補として考えられる文字列をすべて列挙してしまいましょう。

入力

入力は以下の形式で標準入力から与えられる。

N
  • 1 行目にパスワードの長さ N (1 ≦ N ≦ 8) が与えられる。

出力

標準出力に、問題文中の二つの条件をともに満たす文字列すべてを一行に一個ずつ辞書順に出力せよ。
「辞書順」に関しては出力例2の注釈を見よ。
最後の文字列の後ろにも改行を入れること。大文字と小文字は区別される。

入力例1

1

出力例1

a
b
c

入力例2

2

出力例2

aa
ab
ac
ba
bb
bc
ca
cb
cc

(※) 英小文字からなる同じ長さの異なる文字列 s と t について、
次の条件が満たされるとき s は t より辞書順で先となり、そうでなければ s は t より辞書順で後となります。

  • ある整数 i (1 ≦ i ≦ |s| = |t|) が存在し、 1 文字目から i-1 文字目 (両端含む) までは s と t は一致するが、
    i 文字目は一致せず、 s の i 文字目の方がアルファベット順で先である。
例えば、 cabac は cabca より辞書順で先となります (i = 4 とすると条件が成立します) 。