Un gran país antiguo está desarrollando virus con fines militares. Ahora ha encontrado una forma de realizar cálculos en células humanas. Ha diseñado una enzima especial con 4 sitios de unión: uno lee RNA como entrada, otro genera RNA como salida, otro lee y genera RNA hacia delante y atrás para guardar estados temporales del cálculo, y el último lee hacia delante y atrás un RNA que indica los comandos del programa. Necesitan programas de ejemplo (RNA) para una demostración, pero no tienen tiempo suficiente para prepararlos, así que piden tu ayuda.
La enzima trata 3 bases nitrogenadas (G,U,A,C) como una unidad al leer y escribir RNA. No se utilizan las $4^3=64$ combinaciones. Solo se eligen $11$, que se interpretan como datos numéricos o comandos.
Las $11$ combinaciones son:
| Bases nitrogenadas | Valor | Comando |
|---|---|---|
| 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) |
Cuando el sitio de unión de entrada se une a una cadena de RNA, comienza el cálculo. La enzima mueve ese sitio a la primera unidad de datos del RNA de entrada, el sitio del programa a la primera unidad de código del RNA del programa e inicializa el sitio de salida como vacío. También genera un RNA con una sola unidad e inicializa en ella el sitio de unión de estado.
La enzima ejecuta los comandos uno a uno hasta llegar al llamado «marca STOP».
Los comandos son muy sencillos y muy distintos de los lenguajes modernos. Solo hay 9 tipos:
Marca STOP. Detiene la ejecución.
Mueve el sitio de unión de estado a la unidad siguiente. Si está después de la última, añade una unidad $0$.
Mueve el sitio de unión de estado a la unidad anterior. Si está antes de la primera, añade una unidad $0$.
Sustituye la unidad de datos del sitio de estado por la siguiente mayor numéricamente. Si supera el máximo ($9$), sustitúyela por $-1$.
Sustituye la unidad de datos del sitio de estado por la siguiente menor numéricamente. Si baja del mínimo ($-1$), sustitúyela por $9$.
Copia la unidad de datos del sitio de estado al sitio de salida.
Si no hay unidades de entrada, sustituye la unidad del sitio de estado por $-1$. En caso contrario, sustitúyela por la unidad del sitio de entrada y mueve el sitio de unión de entrada a la unidad de datos siguiente.
Si la unidad del sitio de estado no es $0$, mueve el sitio del programa al comando siguiente. En caso contrario, muévelo hacia delante al comando situado después del comando $8$ «correspondiente».
Si la unidad del sitio de estado es $0$, mueve el sitio del programa al comando siguiente. En caso contrario, muévelo hacia atrás al comando situado después del comando $7$ «correspondiente».
«Correspondiente» significa tratar los comandos $7$ y $8$ como los paréntesis ( y ). Deben formar una expresión correctamente emparejada, y los comandos correspondientes son los paréntesis correspondientes. La pareja de comandos $7$ y $8$ se utiliza a menudo como bucle.
Tras ejecutar el comando actual, el sitio del programa avanza al siguiente, excepto para los comandos $0,7,8$.
El problema de demostración es sencillo: leer una secuencia de dígitos no negativos como un número decimal y determinar si es múltiplo de $k$. Además, la longitud del programa y el número de pasos de ejecución no deben superar $10^6$.
Han preparado un simulador (simu.c). La primera línea de su entrada es el programa RNA. Las líneas siguientes son RNA de entrada para ese programa. Utiliza - para representar $-1$ y los símbolos de 0 a 9 para representar del $0$ al $9$. El simulador ejecutará el programa con cada entrada e imprimirá el resultado final y el número de pasos. También acepta un comando especial $9$: cada vez que llega a él imprime el resultado actual, los datos de estado y el número de pasos. La ejecución del comando $9$ no cuenta como paso.
Nota
Puedes descargar el código fuente del simulador de los adjuntos de DOMjudge. Lo encontrarás aquí.
El simulador que evalúa los envíos no acepta el comando $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;
}Entrada
La única línea contiene un entero positivo $k$.
Restricciones
$1\le k\le6$
$1\le n\le10^9$
Salida
El archivo de salida debe contener una línea: el RNA de comandos.
Este programa leerá una secuencia de dígitos no negativos como un entero decimal $n$. Si $n$ es múltiplo de $k$, imprimirá $1$; en caso contrario, $0$.
Tu programa lee y escribe datos numéricos directamente. La enzima los transforma de y a bases nitrogenadas.
La longitud del código RNA no debe superar $10^6$. El número de pasos de ejecución tampoco debe superar $10^6$.
Ejemplos
Entrada 1
1
Salida 1
UCCAGGUACUGUUGCGCGCCC
Entrada 2
2
Salida 2
UGCAGGUACACGAGGUACUGUUGAAGGUACACGUGCUGAUGUUCCUGCUGUACGUGCAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAGCGCCC
Entrada 3
3
Salida 3
UGCAGGACGACGUCCAGGUACACGUGCACGUGCUGAUGAUGUACGACGACGUGCUGAUGCAGGUACACGAGGUACUGUUGAUGUACGAGGUGAUGAUGAUGCUGAAGGUACACGAGGUACUGUUGAUGUACGGCGCCCUGUUGAUGAAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAAGGUACUGAUGCACGUGUUGAAGGUACACGUGCUGAAGGUACACGUGCUGAAGGUACACGUACUACUGAAGGUACACGUGCUGAUGUUGUUGUUGUACGAGGUACUGAUGCACGUGUUGAUGAUGU
Entrada 4
6
Salida 4
UGCAGGACGACGUCCAGGUACACGUGCACGUGCUGAUGAUGUACGACGACGUGCUGAUGCAGGUACACGAGGUACUGUUGAUGUACGAGGUGAUGAUGAUGAAGGAGGUACUGUGCGCCCUGUACGACGACGACGACGACGUGCAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGAGGUACUGAUGCACGAGGUACUGAUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAGCGCCCUGUUGAACGACGAGGUACUGUACGAGGUACUGUUGAUGAUGAUGAAGGUACACGACGACGUGCACGUGCUGAUGAUGAUGAUGUACGACGACGAGGUACUGAUGAUGAUGCACGACGACGUGUUGAUGAUGAAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGAGGUACUGAUGCACGAGGUACUGAUGCACGAGGUACUGAUACUACACGUGUUGUUGUUGUUGUUGUUGUUGUUGUUGAAGGUACUGAUGCACGUGUUGAAGGUACACGUGCUGAAGGUACACGUGCUGAAGGUACACGUACUACUGAAGGUACACGUGCUGAUGUUGUUGUUGUACGAGGUACUGAUGCACGUGUUGAUGAUGU
Nota
Cada salida de ejemplo tiene una sola línea. La dividimos en varias por la disposición del papel. Debes concatenarlas en una sola línea.
A continuación se muestra la ejecución del primer programa de ejemplo.
| Programa | Memoria | Entrada | Salida | Comentario |
|---|---|---|---|---|
| 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 |