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:0.125s
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
2013-04-12 23:22:30 Soh Eu Que Sei
Já encheu a minha pacięncia..TODOS os testes que eu fiz (conferindo na calculadora do windows) e que eu achei na internet funcionam.
Na boa, năo entendo porque fazer um problema onde o desafio é ficar formatando a saída...aff
2012-11-01 21:59:51 Ovídio César
Eu fiz por binário, todas meus testes deram certos, e o Spoj dar como resposta errada. ŹŹ
2012-09-12 17:29:25 Daniela
Também năo entendi o que seria "A entrada termina com final de arquivo."
2012-09-06 21:14:23 Nícolas Estevan [UNISO]
A entrada termina com final de arquivo.???
Este é meu primeiro programa aqui no SPOJ e năo entendi o que é isso...
2012-07-31 14:33:11 Jorge Gabriel [UNIFEI]
Pooo Xuxa VAi Conta o Segredo??
2011-11-18 00:58:09 Filipe Bittencourt [UNIFEI]
ATENÇĂO! EASY.
considere binario a = 0 b = 1...
a = 0 = 0
b = 1 = 1
ab = 01 = 1
ba = 10 = 2
aaaa = 0000 = 0
bbbb = 1111 = 15
aabb = 0011 = 3
abbb = 0111 = 7

Perceberam?... agora é só programar
2011-05-19 16:17:19 Wyllian
@Kelvin
esse erro é causado ou por tentativa de acesso nao permitido da memoria, ou entao vc ta esquecendo de colocar return 0 no final do codigo. Logo, o programa deve ser iniciado como int main ()

abs
2011-04-29 23:31:07
SigSegV o que causa esse erro ?
2010-10-30 22:57:24 Gabriel Pires [UFRJ]
É a soma dos custos de todos os caminhos possíveis e o custo de um caminho é calculado pelo produto dos custos das arestas.

Caso "bbbb":
caminho 1: (p,b) (p,b) (p,b) (p->q,b), custo = 1*1*1*1 = 1

caminho 2: (p,b) (p,b) (p->q,b) (q,b),
custo = 1*1*1*2 = 2

caminho 3: (p,b) (p->q,b) (q,b) (q,b)
custo = 1*1*2*2 = 4

caminho 4: (p->q,b) (q,b) (q,b) (q,b)
custo = 1*2*2*2 = 8

SOMA = 1 + 2 + 4 + 8 = 15

=)
2010-09-25 02:41:03 Eric
Alguém pode me explicar porque a palavra 6 vale 15?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.