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.|

REGISTRA - Registrador de Deslocamento

Um Registrador de Deslocamento é um circuito que desloca de uma posição os elementos de um vetor de bits. O registrador de deslocamento tem uma entrada (um bit) e uma saída (também um bit), e é comandado por um pulso de relógio. Quando o pulso ocorre, o bit de entrada se transforma no bit menos significativo do vetor, o bit mais significativo é jogado na saída do registrador, e todos os outros bits são deslocados de uma posção em direção ao bit mais significativo do vetor (em direção à saída).

Um Registrador de Deslocamento com Retroalimentação Linear (em inglês, lfsr) é um registrador de deslocamento no qual o bit de entrada é determinado pelo valor do ou-exclusivo de alguns dos bits do registrador antes do pulso de relógio. Os bits que são utilizados na retroalimentação do registrador são chamados de torneiras. A figura abaixo mostra um lfsr de 8 bits, com três torneiras (bits 0, 3 e 5).

registrador

Neste problema, você deve escrever um programa que, dados o número de bits de um lfsr, quais bits são utilizados na retroalimentação, um estado inicial e um estado final do lfsr, determine quantos pulsos de relógio serão necessários para que, partindo do estado inicial, o lfsr chegue ao estado final (ou determinar que isso é impossível).

Entrada

A entrada contém vários casos de teste. Cada caso de teste é composto por três linhas. A primeira linha contém dois números inteiros N, T , indicando respectivamente o número de bits (2≤N≤32) e o número de torneiras (2≤T≤N). Os bits são identificados por inteiros de 0 (bit menos significativo) a N - 1 (bit mais significativo). A segunda linha contém T inteiros, separados por espaços, apresentando os identificadores dos bits que são torneiras, em ordem crescente. O bit 0 sempre é uma torneira. A terceira linha contém dois números em notação hexadecimal I e F , separados por um espaço em branco, representando respectivamente o estado inicial e o estado final do lfsr.

O final da entrada é indicado por uma linha que contém dois zeros separados por espaços em branco.

Os dados devem ser lidos da entrada padrão.

Saída

Para cada caso de teste da entrada seu programa deve imprimir uma única linha. Se for possível chegar ao estado final a partir do estado inicial dado, a linha da saída deve conter apenas um inteiro, o menor número de pulsos de relógio necessários para o lfsr atingir o estado final.

Caso não seja possível, a linha deve conter apenas o caractere '*'.

O resultado de seu programa deve ser escrito na saída padrão.

Exemplo

Entrada:
8 3
0 3 5
a9 35
5 2
0 4
1b 2
7 3
0 2 3
4d 1a
0 0


Saída:
3
*
61

Adicionado por:gogo40
Data:2009-11-29
Tempo limite:6.098s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP NODEJS OBJC PERL6 PY_NBC SCALA SQLITE TCL VB.NET
Origem:Primeira Fase da Maratona de Programação - 2009

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