encode/decode

Time Limit : 3 sec, Memory Limit : 131072 KB

K - encode/decode

以下の2条件を全て満たす文字列Tの事を「良い」文字列と呼ぶことにする

  • TはABCDEFGHIの9種類の文字列からなる
  • T上の連続する2文字は次のグラフ上でも隣接している

「良い」文字列の例

  • BEB
  • ABCDCBEFGHI

「良い」文字列ではない例

  • AC(AとCは隣接していない)
  • AABCD(同じ文字はグラフ上では隣接していないとみなす)

以下の条件を満たすような2つの関数,encodeとdecodeを実装せよ.

  • 任意の01列Sに対し,encode(S)は「良い」文字列である
  • 任意の01列Sに対し,decode(encode(S))=Sを満たす

入出力形式

この問題にはencodeフェーズとdecodeフェーズがあり, それぞれ独立にプログラムが実行される.

encodeフェーズのとき, 入力は以下の形式で与えられる.

encode
N
S

Nは与えられる01列Sの長さである. Sはあなたがencodeするべき01列である. この時の,あなたが提出するプログラムの出力をTとする. Tが良い文字列でない場合は不正解となり,decodeフェーズは実行されない. decodeフェーズのとき,入力は以下の形式で与えられる.

decode
M
T

Tはencodeフェーズにおけるあなたの出力である. Mは文字列Tの長さである. この時の,あなたが提出するプログラムの出力がencodeフェーズにおけるSと一致する場合,正解となる

採点方式

この問題では入力Sに対する出力encode(S)の長さに応じて得点が決まる.

全てのテストケースについて, |encode(S)| ≦ |S| + 10 を満たすときこの問題に対する得点が満点となる.

また, |encode(S)| ≦ 2×|S| + 10 を満たす場合, この問題に対する得点は50点となる.

制約

  • 1 ≤ N ≤ 300000

入出力例

encodeフェーズ

入力

encode
6
001100

出力

ABCBE

encodeフェーズの終了後あなたのプログラムは一旦終了し,次にdecodeフェーズが開始する

decodeフェーズ

入力

decode
5
ABCBE

出力

001100

Source: Kyoto University Programming Contest 2013 , Kyoto, Japan, 2013-07-06
http://www.kupc.jp/
http://kupc2013.contest.atcoder.jp/