시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1 | 0 | 0 | 0.000% |
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 sequência de termos tal que:
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 sequê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.
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.
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 sequências de termos. Se mais de uma sequência é possível, elas devem aparecer em ordem lexicográfica crescente. Cada sequê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 sequências Sa = a1a2 ... am e Sb = b1b2 ... bn. Sa precede Sb em ordem lexicográfica se e apenas se Sb é não-vazia e uma das seguintes condições é verdadeira:
7 1 10 2 230 3 6311 4 2 2 -1 -1
#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