오래된 거대한 고대 국가가 군사 목적으로 바이러스를 개발하고 있다. 현재 인간 세포 안에서 계산하는 방법을 찾았다. 이들은 특별한 효소를 설계했다. 효소에는 결합 부위가 4개 있다. 하나는 입력 RNA를 읽고, 하나는 출력 RNA를 생성한다. 하나는 임시 계산 상태를 유지하도록 RNA를 앞뒤로 읽고 생성하며, 마지막 하나는 프로그램 명령을 나타내는 RNA를 앞뒤로 읽는다. 시연할 예제 프로그램(RNA)이 필요하지만 준비할 시간이 부족하여 당신에게 도움을 요청했다.
효소는 RNA를 읽고 쓸 때 뉴클레오베이스(G,U,A,C) 3개를 하나의 단위로 처리한다. $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의 첫 코드 단위로 옮긴다. 출력 결합 부위를 비어 있는 상태로 초기화하고, 단위 하나만 포함한 RNA를 생성하여 상태 결합 부위를 그 단위에 초기화한다.
효소는 “STOP 표시”라는 명령에 도달할 때까지 프로그램 명령을 하나씩 실행한다.
명령은 현대 프로그래밍 언어와 달리 매우 간단하다. 명령은 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)이 준비되어 있다. 시뮬레이터 입력의 첫 줄은 RNA 프로그램이고, 그 이후의 줄들은 RNA 프로그램의 입력 RNA이다. 입력에서 -로 $-1$을, 0부터 9로 $0$부터 $9$를 나타낸다. 시뮬레이터는 각 입력 데이터에 대해 프로그램을 실행하고 최종 결과와 실행 단계 수를 출력한다. 특별 명령 $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인 한 줄이 있어야 한다.
이 프로그램은 음이 아닌 숫자들의 연속을 십진 정수 $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
참고
각 예제 출력은 한 줄뿐이다. 종이 배치 때문에 예제에서 여러 줄로 나누었다. 이들을 한 줄로 이어 붙여야 한다.
다음은 첫 번째 예제 프로그램의 실행 예이다.
| 프로그램 | 메모리 | 입력 | 출력 | 설명 |
|---|---|---|---|---|
| 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 |