ある大きな古い国が軍事目的でウイルスを開発しています。現在、人間の細胞内で計算する方法を見つけました。特別な酵素を設計し、それには 4 つの結合部位があります。1 つは入力 RNA の読み取り、1 つは出力 RNA の生成に使います。1 つは一時的な計算状態を保持するため RNA を前後に読み書きし、最後の 1 つはプログラムの命令を表す RNA を前後に読み取ります。実演用のサンプルプログラム（RNA）が必要ですが、準備する時間が足りないので、あなたに助けを求めました。
酵素は RNA の読み書きで 3 個の核酸塩基（G,U,A,C）を 1 単位として扱います。$4^3=64$ 通りすべてを使うわけではなく、$11$ 通りだけを選び、数値データまたは命令として解釈します。
$11$ 通りの組合せは次のとおりです。
| 核酸塩基 | 値 | 命令 |
|---|---|---|
| GAC | $-1$ | |
| CCC | $0$ | STOP |
| ACG | $1$ | NEXT |
| UGA | $2$ | PREV |
| UGC | $3$ | INC |
| UAC | $4$ | DEC |
| GCG | $5$ | OUT |
| UCC | $6$ | IN |
| AGG | $7$ | BEGIN |
| UGU | $8$ | END |
| CAC | $9$ | (DEBUG) |
酵素の入力結合部位が RNA 鎖に付くと計算が始まります。入力結合部位を入力 RNA の最初のデータ単位へ、プログラム結合部位をプログラム RNA の最初のコード単位へ移し、出力結合部位を空に初期化します。そして 1 単位だけを含む RNA を生成し、状態結合部位をそこに初期化します。
酵素は「STOP マーク」と呼ばれる命令に達するまで命令を 1 つずつ実行します。
命令は現代のプログラミング言語と大きく異なり、とても単純です。9 種類しかありません。
STOP マーク。実行を停止します。
状態結合部位を次の単位へ移します。最後の単位を越えたら $0$ の単位を置きます。
状態結合部位を前の単位へ移します。最初の単位より前なら $0$ の単位を置きます。
状態結合部位のデータ単位を数値的に次に大きいものに置き換えます。最大値（$9$）を越えたら $-1$ に置き換えます。
状態結合部位のデータ単位を数値的に次に小さいものに置き換えます。最小値（$-1$）より小さくなったら $9$ に置き換えます。
状態結合部位のデータ単位を出力部位へコピーします。
入力データ単位がなければ状態結合部位のデータ単位を $-1$ に置き換えます。そうでなければ入力部位のデータ単位に置き換え、入力結合部位を次のデータ単位へ移します。
状態結合部位のデータ単位が $0$ でなければ、プログラム結合部位を次の命令へ移します。そうでなければ「対応する」命令 $8$ の直後の命令へ前進します。
状態結合部位のデータ単位が $0$ なら、プログラム結合部位を次の命令へ移します。そうでなければ「対応する」命令 $7$ の直後の命令へ後退します。
「対応する」とは、命令 $7$ と $8$ を括弧 ( と ) とみなすことです。正しい括弧式を形成しなければならず、対応する命令は対応する括弧に当たります。命令 $7$ と $8$ の組はよくループに使われます。
命令 $0,7,8$ 以外では、現在の命令実行後にプログラム結合部位が次の命令へ移ります。
実演の課題は単純です。非負の数字の列を十進数として読み込み、それが $k$ の倍数か判定します。さらにプログラム長と実行ステップ数は $10^6$ を越えてはいけません。
シミュレーションプログラム（simu.c）が用意されています。シミュレータの入力の 1 行目は RNA プログラムで、以降の行はそのプログラムへの入力 RNA です。入力では - が $-1$、0 から 9 が $0$ から $9$ を表します。各入力についてプログラムを実行し、最終結果と実行ステップ数を出力します。特別な命令 $9$ も受け付け、そこに達するたびに現在の結果、状態データ、実行ステップ数を出力します。命令 $9$ の実行はステップ数に数えません。
注記
シミュレータのソースコードは DOMjudge の添付ファイルからダウンロードできます。ここにあります。
提出を判定するシミュレータは命令 $9$ を受け付けません。
/* simu.c */
/* gcc -o simu simu.c */
#include <stdio.h>
#include <string.h>
char *cmds[10] =
{ "CCC", "ACG", "UGA", "UGC", "UAC"
, "GCG", "UCC", "AGG", "UGU", "CAC"
};
char code[1000002], memory[2000001], input[1000001];
static inline int get_cmd(char *code){
for(int i=9; i>=0; --i)
if( strncmp(cmds[i], code, 3)==0 )
return i;
return -1;
}
int main(){
if( !fgets(code, 1000002, stdin) ){
puts("no code");
return 1;
}
int code_len = strlen(code);
if( code[code_len-1]!='\n' ){
puts("code too long");
return 1;
}
code[--code_len] = 0;
while( fgets(input, 1000001, stdin) ){
char *ip = code, *input_p = input;
char *mem = memory + 1000000;
char *mem_begin=mem, *mem_end=mem;
*mem = 0;
int step = 0, eof = 0;
while(1){
if( step == 1000000 ){
puts("step out of bound");
break;
}
if( code+code_len-ip < 3 ){
puts("code out of bound");
break;
}
int cmd = get_cmd(ip);
if( cmd<0 ){
printf("invalid code point: %c%c%c\n",
ip[0], ip[1], ip[2]);
break;
}
if( cmd==0 ){
puts("stop normally");
break;
}
if( cmd==1 ){
++mem;
if( mem>mem_end )
*++mem_end = 0;
}
else if( cmd==2 ){
--mem;
if( mem<mem_begin )
*--mem_begin = 0;
}
else if( cmd==3 ){
if( *mem==9 )
*mem = -1;
else
++*mem;
}
else if( cmd==4 ){
if( *mem==-1 )
*mem = 9;
else
--*mem;
}
else if( cmd==5 ){
if( *mem==-1 )
putchar('-');
else
putchar('0' + *mem);
}
else if( cmd==6 ){
while(1){
if( !*input_p || *input_p=='\n' ){
*mem = -1;
break;
}
if( *input_p=='-' ){
*mem = -1;
++input_p;
break;
}
if( '0'<=*input_p && *input_p<='9' ){
*mem = *input_p++ - '0';
break;
}
++input_p;
}
}
else if( cmd==7 ){
if( !*mem ){
int skip = 1;
while(skip){
ip += 3;
if( code+code_len-ip < 3 ){
puts("7 can't find matched 8");
goto END;
}
if( strncmp(cmds[8], ip, 3)==0 )
--skip;
else if( strncmp(cmds[7], ip, 3)==0 )
++skip;
}
}
}
else if( cmd==8 ){
if( *mem ){
int skip = 1;
while(skip){
ip -= 3;
if( ip < code ){
puts("8 can't find matched 7");
goto END;
}
if( strncmp(cmds[7], ip, 3)==0 )
--skip;
else if( strncmp(cmds[8], ip, 3)==0 )
++skip;
}
}
}
else if( cmd==9 ){
printf("\nstep: %d, state: ", step);
for(char *p=mem_begin; p<=mem_end; ++p)
if( p==mem )
printf("[%c]", *p<0 ? '-' : '0'+*p);
else
putchar(*p<0 ? '-' : '0'+*p);
printf(", code:");
for(char *p=code; p<code+code_len; p+=3)
printf("%c%c%c%c",
p==ip ? '[' : p==ip+3 ? ']' : ' ',
p[0], p[1], p[2]);
if( code+code_len==ip+3 )
putchar(']');
puts("");
--step;
}
++step;
ip += 3;
}
END:;
}
return 0;
}入力
唯一の行に正の整数 $k$ が含まれます。
制約
$1\le k\le6$
$1\le n\le10^9$
出力
出力ファイルには命令 RNA を表す 1 行が含まれる必要があります。
このプログラムは非負の数字の列を十進整数 $n$ として読みます。$n$ が $k$ の倍数なら $1$、そうでなければ $0$ を出力します。
プログラムは数値データを直接読み書きします。酵素が数値データと核酸塩基の間の変換を行います。
RNA コード長は $10^6$ 以下でなければなりません。実行ステップ数も $10^6$ 以下でなければなりません。
入出力例
入力 1
1
出力 1
UCCAGGUACUGUUGCGCGCCC
入力 2
2
出力 2
UGCAGGUACACGAGGUACUGUUGAAGGUACACGUGCUGAUGUUCCUGCUGUACGUGCAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAGCGCCC
入力 3
3
出力 3
UGCAGGACGACGUCCAGGUACACGUGCACGUGCUGAUGAUGUACGACGACGUGCUGAUGCAGGUACACGAGGUACUGUUGAUGUACGAGGUGAUGAUGAUGCUGAAGGUACACGAGGUACUGUUGAUGUACGGCGCCCUGUUGAUGAAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAAGGUACUGAUGCACGUGUUGAAGGUACACGUGCUGAAGGUACACGUGCUGAAGGUACACGUACUACUGAAGGUACACGUGCUGAUGUUGUUGUUGUACGAGGUACUGAUGCACGUGUUGAUGAUGU
入力 4
6
出力 4
UGCAGGACGACGUCCAGGUACACGUGCACGUGCUGAUGAUGUACGACGACGUGCUGAUGCAGGUACACGAGGUACUGUUGAUGUACGAGGUGAUGAUGAUGAAGGAGGUACUGUGCGCCCUGUACGACGACGACGACGACGUGCAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAGCGCCCUGUUGAACGACGAGGUACUGUACGAGGUACUGUUGAUGAUGAUGAAGGUACACGACGACGUGCACGUGCUGAUGAUGAUGAUGUACGACGACGAGGUACUGAUGAUGAUGCACGACGACGUGUUGAUGAUGAAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAAGGUACUGAUGCACGUGUUGAAGGUACACGUGCUGAAGGUACACGUGCUGAAGGUACACGUACUACUGAAGGUACACGUGCUGAUGUUGUUGUUGUACGAGGUACUGAUGCACGUGUUGAUGAUGU
注記
各出力例は 1 行だけです。紙面の都合で複数行に分けています。これらをつなげて 1 行にしてください。
以下は最初のサンプルプログラムの実行例です。
| プログラム | メモリ | 入力 | 出力 | コメント |
|---|---|---|---|---|
| UCC AGG UAC UGU UGC GCG CCC | $3$ | |||
| UCC AGG UAC UGU UGC GCG CCC | $3$ | IN | ||
| UCC AGG UAC UGU UGC GCG CCC | $3$ | BEGIN: $3 e0$ | ||
| UCC AGG UAC UGU UGC GCG CCC | $2$ | DEC | ||
| UCC AGG UAC UGU UGC GCG CCC | $2$ | END: $2 e0$ | ||
| UCC AGG UAC UGU UGC GCG CCC | $1$ | DEC | ||
| UCC AGG UAC UGU UGC GCG CCC | $1$ | END: $1 e0$ | ||
| UCC AGG UAC UGU UGC GCG CCC | $0$ | DEC | ||
| UCC AGG UAC UGU UGC GCG CCC | $0$ | END: $0=0$ | ||
| UCC AGG UAC UGU UGC GCG CCC | $1$ | INC | ||
| UCC AGG UAC UGU UGC GCG CCC | $1$ | $1$ | OUT | |
| UCC AGG UAC UGU UGC GCG CCC | $1$ | $1$ | STOP |