Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PARADA - O problema da parada

O Problema da Parada (The Halting Problem) é um problema de decisão clássico da Ciência da Computação que consiste, basicamente, em determinar se um dado programa sempre vai parar (ou seja, terminar sua execução) para uma dada entrada arbitrária ou se vai executar infinitamente. Alan Turing provou, em 1936, que é impossível resolver o problema da parada generalizando para qualquer par programa-entrada. Neste problema, porém, dada a descrição de uma linguagem simples, um programa escrito nessa linguagem e uma entrada para esse programa, você deve determinar se o programa dado pára com a entrada dada e, em caso positivo, qual a saída produzida.

Esta linguagem só trabalha com números inteiros de 0 a 999 (inclusive). Sendo assim, o sucessor de 999 é 0, e o antecessor de 0 é 999. Além disso, ela possui dez variáveis (R0 a R9), sendo que a R0 sempre é atribuído o valor de chamada do programa (ou seja, o parâmetro de entrada) e a R9 é sempre atribuído o valor de saída (o retorno). No início da execução do programa, é atribuído o valor 0 a todas as variáveis, com exceção de R0 que recebe o parâmetro de entrada.

As operações básicas são atribuição (MOV), soma (ADD), subtração (SUB), multiplicação (MUL), divisão inteira (DIV) e resto da divisão inteira (MOD). Todas essas operações têm a sintaxe COMANDO OPERANDO1,OPERANDO2 (sem espaços entre a vírgula e os operandos), onde COMANDO é uma dessas operações, OPERANDO1 é uma das 10 variáveis (R0 a R9) e OPERANDO2 pode ser uma das 10 variáveis ou um valor inteiro (entre 0 e 999). Todas as operações modificam o valor de OPERANDO1, sendo assim MOV R4,100 é o equivalente a atribuir o valor 100 a R4, enquanto que MUL R3,R8 é o equivalente a multiplicar R3 por R8 e atribuir o resultado a R3. A operação DIV, assim como a MOD, retornam 0 (zero) se OPERANDO2 for 0 ou se a variável equivalente tiver valor 0. Ou seja, DIV R4,0 é o equivalente a MOV R4,0. Por divisão inteira, entendemos a parte inteira do quociente da divisão (sem a parte fracionária). Por exemplo, a divisão inteira de 7 por 2 é 3 (sendo o resto 1).

Existem seis comandos de fluxo de decisão: IFEQ (se igual), IFNEQ (se diferente), IFG (se maior), IFL (se menor), IFGE (se maior ou igual) e IFLE (se menor ou igual). A sintaxe de todos eles é COMANDO OPERANDO1,OPERANDO2 (sem espaços entre a vírgula e os operandos), onde OPERANDO1 e OPERANDO2 podem ser variáveis (R0 a R9) ou valores inteiros (entre 0 e 999). Assim, o comando IFEQ R4,123 é o equivalente a testar se R4 é igual a 123. Caso a condição testada seja verdadeira, o programa continua a executar normalmente a linha subseqüente ao comando de decisão. Caso a condição seja falsa, o programa passa a executar a linha subseqüente ao ENDIF mais próximo. Todos os comandos de decisão devem ter um comando ENDIF correspondente.

Finalmente, existem os comandos CALL e RET, ambos com a sintaxe COMANDO OPERANDO, onde OPERANDO é uma variável (R0..R9) ou valor direto (entre 0 e 999). O comando CALL chama o próprio programa novamente, passando OPERANDO como parâmetro de entrada, ou seja, atribuindo o valor de OPERANDO à variavel R0. Já RET termina a execução do programa, retornando o valor de OPERANDO como o resultado de saída. A ultima linha do programa sempre será um comando RET. Observe que, caso o programa chame a si mesmo através do comando CALL, quando a execução voltar, o valor de R9 vai estar alterado com o valor retornado pelo programa. Note também que todas as variáveis (R0..R9) são locais, ou seja, uma chamada subseqüente ao programa não pode alterar os valores guardados nas variáveis da instância anterior, com exceção, naturalmente, do valor de R9 que recebe o retorno da instância chamada.

O exemplo a seguir ilustra um programa que calcula o fatorial de um número.

 

linha  comando
1 IFEQ R0,0
2 RET 1
3 ENDIF
4 MOV R1,R0
5 SUB R1,1
6 CALL R1
7 MOV R2,R9
8 MUL R2,R0
9 RET R2

1a linha: Verifica se o valor de R0 vale 0, caso positivo, executa a próxima linha, caso contrário, pula para a 4a linha (ENDIF mais próximo).
2a linha: Retorna 1 como saída do programa.
3a linha: Marca o fim do bloco de decisão iniciado na primeira linha.
4a linha: Atribui o valor de R0 a R1 (R1 ← R0).
5a linha: Diminui 1 de R1 (R1 ← R1 - 1).
6a linha: Chama o programa passando R1 como parâmetro de entrada.
7a linha: Guarda o valor de R9 (retornado pela chamada anterior) em R2 (R2 ← R9)
8a linha: Multiplica o valor de R2 por R0 (R2 ← R2 * R0)
9a linha: Retorna o valor de R2 como saída do programa.

A tabela seguir traz um resumo dos comandos para referência:

 

comando     	sintaxe                  significado
MOV MOV OP1,OP2 OP1 ← OP2
ADD ADD OP1,OP2 OP1 ← OP1 + OP2
SUB SUB OP1,OP2 OP1 ← OP1 - OP2
MUL MUL OP1,OP2 OP1 ← OP1 * OP2
DIV DIV OP1,OP2 OP1 ← OP1 / OP2
MOD MOD OP1,OP2 OP1 ← OP1 % OP2
IFEQ IFEQ OP1,OP2 if OP1 == OP2
IFNEQ IFNEQ OP1,OP2 if OP1 != OP2
IFG IFG OP1,OP2 if OP1 > OP2
IFL IFL OP1,OP2 if OP1 < OP2
IFGE IFGE OP1,OP2 if OP1 >= OP2
IFLE IFLE OP1,OP2 if OP1 <= OP2
ENDIF ENDIF Marca fim do bloco de execução condicional
CALL CALL OP Chama o programa com OP como entrada
RET RET OP return OP

Entrada

A entrada contém vários casos de teste. Cada caso de teste se inicia com dois inteiros, L e N, representando respectivamente o número de linhas do programa (1 ≤ L < 100) e o valor do parâmetro de entrada do programa (0 ≤ N < 1000). As L linhas seguintes contêm o programa. Pode-se assumir que ele está sempre sintaticamente correto de acordo com as regras definidas acima. Todos os comandos (bem como o nome das variáveis) só conterão letras maiúsculas. O final da entrada é marcado pelo caso em que L = N = 0 e não deve ser processado.

Saída

Para cada caso de teste, seu programa deve produzir uma linha contendo um inteiro que representa o valor de saída (retorno) para a entrada N dada, ou um asterisco (*) no caso de o programa nunca terminar.

Exemplo de entrada

 

9 6
IFEQ R0,0
RET 1
ENDIF
MOV R1,R0
SUB R1,1
CALL R1
MOV R2,R9
MUL R2,R0
RET R2
2 123
CALL R0
RET R0
0 0

Saída para o exemplo de entrada

 

720
*

Adicionado por:Wanderley Guimarăes
Data:2009-09-30
Tempo limite:1.230s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Primeira fase da Maratona de Programação - 2006

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.