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

TECLE - Tecle e Some

Strike Boy, como o apelido sugere, é um garoto fanático por todo tipo de jogos em computador. Ele está passando as férias em uma ilha paradisíaca, onde computadores não são permitidos. Ele se divertiu por algum tempo com os jogos em seu telefone celular, mas a bateria acabou e não há eletricidade na ilha, de forma que ele parou de jogar. Strike Boy então decidiu inventar um novo passatempo, usando o teclado de seu telefone celular. Neste novo jogo, para dois jogadores, um deles escolhe dois inteiros S e D. O jogador oponente deve então encontrar uma seqüência de termos tal que:

• cada termo da seqüência é um número com D dígitos decimais, exceto pelo ultimo termo, que pode ter entre 1 e D dígitos;

• a soma de todos os termos da seqüência é igual a S;

• os dígitos utilizados para formar um termo correspondem às teclas de um teclado padrão de telefone celular (‘0’ a ‘9’);

• cada dígito é utilizado no máximo uma vez na seqüência;

• o primeiro termo de uma seqüência pode começar com qualquer dígito, mas a ordem dos dígitos da seqüência, quando lidos da esquerda para a direita, é tal que a próxima tecla corresponde sempre a uma tecla imediatamente vizinha da tecla utilizada previamente (na vertical, na horizontal ou na diagonal).

Por exemplo, se S = 230 e D = 3, há apenas duas soluções possíveis obedecendo as regras do jogo: [074, 156] e [085, 142, 3]. A seqüência [230] não é uma solução porque a tecla ‘3’ não é vizinha da tecla ‘0’.

Ajude Strike Boy a verificar se as respostas do oponente estão corretas: escreva um programa que, dados S e D, imprima todas as soluções possíveis.

Entrada

A entrada contém vários casos de teste. Cada caso de teste consiste em apenas uma linha, contendo dois inteiros S e D, separados por um espaço, representando a soma desejada e o número de dígitos de cada termo (0 <= S <= 10.000.000.000 e 1 <= D <= 10). O final da entrada é indicado por S = D = −1.

Saída

Para cada caso de teste da entrada seu programa deve produzir uma resposta. A primeira linha de uma resposta deve conter um identificador do caso de teste, no formato ‘#i’, onde ‘i’ tem inicialmente o valor 1 e é incrementado a cada caso de teste. Então, se uma solução para o passatempo existe, seu programa deve produzir uma lista das possíveis seqüências de termos. Se mais de uma seqüência é possível, elas devem aparecer em ordem lexicográfica crescente. Cada seqüência de termos deve ser impressa em uma linha, com os termos separados por um espaço em branco. Se não há solução, seu programa deve imprimir uma linha contendo a palavra ‘impossivel’ (note ausência de acentuação).

Definição: considere as seqüências Sa = a1 a2 ...am e Sb = b1 b2 . . . bn. Sa precede Sb em ordem lexicográfica se e apenas se Sb é não-vazia e uma das seguintes condições é verdadeira:

• Sa é uma seqüência vazia;

• a1 < b1; • a1 = b1 e a seqüência a2 a3 . . . am precede a seqüência b2 b3 . . . bn.

Exemplo de entrada

 

7 1
10 2
230 3
6311 4
2 2
-1 -1

Saída para o exemplo de entrada

#1
0 7
1 2 4
1 4 2
2 1 4
2 4 1
2 5
4 1 2
4 2 1
5 2
7
7 0
#2
impossivel
#3
074 156
085 142 3
#4
0896 5412 3
0986 5321 4
0986 5324 1
0987 5324
#5
2

 


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

hide comments
2009-07-29 19:07:31 Carlos Eduardo Rodrigues Alves [USJT]
Seria bom colocar qual é a disposição das teclas em um telefone celular padrão...

Pelo texto original, é
1 2 3
4 5 6
7 8 9
* 0 #

Last edit: 2009-07-29 19:08:31
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.