問題一覧 > 通常問題

No.2671 NUPC Decompressor

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 146
作問者 : 👑 eoeoeoeo / テスター : XelmephXelmeph 👑 nu50218nu50218 👑 nullnull ngtkanangtkana NokonoKotlinNokonoKotlin
3 ProblemId : 10411 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-15 21:21:35

問題文

長さ $8$ の文字列 $S = S_1 S_2 \cdots S_8$ が以下の2つの条件を満たすとき、 $S$ をNUPC圧縮文字列とよびます。

  • 奇数番目の文字 $S_1, S_3, S_5, S_7$ は、それぞれ順に N, U, P, C である。
  • 偶数番目の文字 $S_2, S_4, S_6, S_8$ は、 1 または 2 である。

NUPC圧縮文字列 $S$ は、名前のとおり、ある文字列を圧縮したものです。 以下の手順で解凍することで、圧縮前の文字列 $T$ が得られます。

  1. $T$ を長さ $0$ の文字列とする。
  2. $i = 1, 2, \dots, 8$ に対し、順に以下の操作を行う。
    • $i$ が奇数のとき、 $T$ の末尾に $S_i$ を加える。
    • $i$ が偶数のとき、
      • $S_i$ が 1 ならば、何もしない。
      • $S_i$ が 2 ならば、 $T$ を「 $T$ と $T$ を連結した文字列」で置き換える。

さて、NUPC圧縮文字列は全部で $16$ 種類存在します。 整数 $1 \leq K \leq 16$ が与えられるので、 NUPC圧縮文字列を解凍して得られる文字列すべて のうち、辞書順で $K$ 番目に小さいものを出力してください。

入力

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

$K$

出力

標準出力へ一行で出力し、最後に改行してください。

制約

入力は以下の制約を満たします。

  • $K$ は $1 \leq K \leq 16$ を満たす整数である。

サンプル

サンプル1
入力
1
出力
NNUNNUPC

辞書順で1番目に小さいものは NNUNNUPC です。 これはNUPC圧縮文字列 N2U2P1C1 を解凍して得られます。

文字列 N2U2P1C1 を解凍するとき、解凍手順で各 $i = 1, 2, \dots, 8$ に対して操作を行った後の $T$ の値は以下のとおりです。

  1. N
  2. NN
  3. NNU
  4. NNUNNU
  5. NNUNNUP
  6. NNUNNUP
  7. NNUNNUPC
  8. NNUNNUPC
サンプル2
入力
5
出力
NNUPC

これはNUPC圧縮文字列 N2U1P1C1 を解凍して得られる文字列です。

サンプル3
入力
13
出力
NUPC

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。