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

CONTAGEM - Não é Mais um Joguinho Canadense

O Canadá é um país muito frio. Em 8 meses por ano as temperaturas praticamente impedem que as ruas sejam ocupadas por vida inteligente, restando apenas criaturas resistentes ao frio como alces, ursos e canadenses (He he he, brincadeirinha...). Nestes longos meses de inverno famílias buscam diversão em frente de suas lareiras (ou, para as mais corajosas, ao redor de suas fogueiras). A família Smith, de Banff, inventou o jogo que descrevemos a seguir.

A brincadeira começa com uma das crianças desenhando um diagrama com estados (representados por bolinhas) ligados por transições (flechas ligando os estados). Cada transição tem uma letra e um número associados. Podemos fazer diversos passeios neste diagrama, partindo de um estado inicio caminhando por suas transições e terminando em um estado final. Um passeio forma uma palavra (obtida da concatenação das letras das transições percorridas) e tem um custo (que é dado pelo produto dos números destas transições).

Exemplo. Considere o diagrama abaixo.

   .--- .---. --.
1b |    | p |   | 1a
   '->  '---' <-'
          |
          | 1b
          |
          V
   .--  .---. --.
2b |    | q |   | 2a
   '->  '---' <-'

Todos os passeios iniciam no estado p e terminam em q.

O passeio que segue pelas transições (p,1a), (p,1a), (p,1b) e termina no estado q forma a palavra aab concatenando as letras de cada transição tem custo 1 (produto dos números destas transições).

O passeio que segue pelas transições (p,1a), (p,1a), (p,1b), (q,2b) e termina no estado q forma a palavra aabb e tem custo 2.

O jogo inventado pelo papai Smith era o seguinte. Depois de desenhar um diagrama como esse, um dos membros da família falava uma palavra, e os outros deveriam descobrir a soma dos custos de todos os passeios no diagrama que formam a palavra dada tais que iniciam no estado p e terminam no estado q. No caso do exemplo do diagrama acima, se o Sr. Smith pedisse a palavra aba a resposta deveria ser 2.

Entrada

A entrada é composta de diversas palavras (o diagrama é sempre o da figura). Cada instância é dada por uma linha contendo uma palavra. Uma palavra é uma seqüência de letras [a,b] com no máximo 60 letras.

A entrada termina com final de arquivo.

Saída

Para cada instância, você deverá imprimir um identificador Palavra k, onde k é o número da instância atual. Na linha seguinte imprima a soma dos custos.

Após cada instância imprima uma linha em branco.

Exemplo

Entrada:
a
b
ab
ba
aaaa
bbbb
aabb
abbb

Saída:
Palavra 1
0

Palavra 2
1

Palavra 3
1

Palavra 4
2

Palavra 5
0

Palavra 6
15

Palavra 7
3

Palavra 8
7

Adicionado por:Wanderley Guimarăes
Data:2007-08-16
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Seletiva para Maratona de Programação do IME - 2007

hide comments
2017-04-16 23:40:56
Tratem a possibilidade de haver uma linha vazia no meio ou no fim da entrada. Fez meu código ser aceito.
2015-12-28 15:28:08
A variavel que deve ser usada é long long pessoal para c++, em java não tem como fazer mesmo, tinha tentado usando long, e agora fui tentar utilizando double(64bits), mas não vai
2015-12-21 16:51:18
Em Java < 8 esse problema não funciona simplesmente por Java não suporte variaveis do tipo Unsigned.
Apesar da variavel long ser 64 bits ela não é unsigned , logo é impossível faze-la em Java, talvez agora com o Java 8, mas não consegui fazer, só em c++ em um código que peguei da internet.
2015-03-04 19:23:16 Italo Rodrigo
Pra quem tá levando WA, tem caso com overflow. Usem um long int para o resultado.
2014-12-15 23:40:16 Bernardo Amorim
Posso considerar que a resposta nunca dá overflow no int ?
2014-08-31 19:14:49 Bernardo Costa


Last edit: 2014-09-01 00:36:27
2013-11-22 21:41:00 Claudio Coutinho [UFPA]
Pra quem năo entendeu, o problema procura o seguinte:

- para cada entrada, o programa deve retornar o custo dela.
- o custo da palavra é a SOMA de todos os PRODUTOS dos passeios POSSÍVEIS para palavras que PERMITEM o início em p e o término em q.
- Exemplo: 'a' tem custo 0, pois năo caminhos possíveis que em que ele termine em q.
--'b' tem custo 1, pois há apenas UM caminho possível que comece em p e termine em q.
-- a palavra 'bbbb' possui os seguintes passeios possíveis:

1: (p,1b) -> (p,1b) -> (p,1b) -> (q,1b) = 1*1*1*1 = 1;
2: (p,1b) -> (p,1b) -> (q,1b) -> (q,2b) = 1*1*1*2 = 2;
3: (p,1b) -> (q,1b) -> (q,2b) -> (q,2b) = 1*1*2*2 = 4;
4: (p,1b) -> (q,2b) -> (q,2b) -> (q,2b) = 1*2*2*2 = 8;

RESPOSTA: Soma dos custos de cada passeio = 1 + 2 + 4 + 8 = 15.
2013-10-27 02:41:47 Daniel
Não consigo entender esse problema, essas transições estão mal explicadas. Se fosse como o amigo falou ali do binário, seria bem fácil, mas não da certo :/
2013-05-20 02:24:07 Bruno Cesar [EACH - USP]
Aos que perguntaram por o que significa:
"A entrada termina com final de arquivo."
isso significa que o ultimo caractere da entrada será um caractere EOF (End Of File)

Last edit: 2013-05-20 02:24:46
2013-04-27 12:30:12 Douglas Oliveira Godinho
O problema realmente é muito confuso, mas o resultado é a soma do produto dos possíveis caminhos (isso está bem nas entrelinhas). Estou me decepcionando com os problemas brasileiros. A lógica de binários năo faz sentido para alguns casos de teste. CUIDADO!

Last edit: 2013-04-27 12:31:07
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.