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

MAPABOLH - Mapas bolha

Bolhas ltda. está desenvolvendo uma nova tecnologia para navegar em um mapa com diferente niveis de ampliação. A nova tecnologia deles assume que uma região a ser mapeada é uma superficie plana retangular e divide esta superficie em sub-regiões retangulares, que representam níveis de ampliação mais profundos.

A tecnologia da Bolhas ltda. representa mapas usando uma estrutura conhecida como quad-tree. Em uma quad-tree, uma região retangular chamada x pode ser dividida na metade, tanto horizontalmente quanto verticalmente, resultando em quatro sub-regiões retangulares de mesmo tamanho. Estas sub-regiões são chamadas regiões filhas de x, e são nomeadas xp para a região superior-esquerda, xq para a região superior-direita, xr para a região inferior-direita e xs para a região inferior-esquerda, onde xc representa a concatenação da string x com o caracter c = 'p', 'q', 'r' ou 's'. Por exemplo, se a região base a ser mapeada se chama m, as regiões filhas de m são, a partir do canto superior-esquerdo na ordem horária: mp, mq, mr e ms, como ilustrado a seguir.

mp mq
ms mr

Qualquer região pode ser subdividida novamente. Por exemplo, a região chamada ms pode ser novamente dividida nas subregiões msp, msq, msr e mss, como ilustrado a seguir.

msp msq
mss msr

Um outro exemplo, a figura a seguir mostra o resultado da subdivisão das sub-regiões filhas da região chamada msr.

msrpp msrpq msrqp msrqq
msrps msrpr msrqs msrqr
msrsp msrsq msrrp msrrq
msrss msrsr msrrs msrrr

Sub-regiões com nomes de mesmo comprimento tem o mesmo nível de ampliação, desde que elas representem regiões de mesmo tamanho. Sub-regiões no mesmo nível de ampliação que compartilham um lado comum são ditas vizinhas.

Qualquer coisa que esteja fora da região base m não é mapeada e, para todos os niveis de ampliação, todas sub-regiões de m são mapeadas.

A tecnologia dos mapas bolha fornece um modo para o usuário navegar de uma dada sub-região para sub-regiões vizinhas nas direções cima, baixo, esquerda e direita. Sua missão é ajudar a Bolhas ltda. a encontrar as sub-regiões vizinhas de uma dada sub-região. Isto é, dado o nome de uma sub-região retangular, você deve determinar os nomes de suas quatro sub-regiões vizinhas.

Entrada

A entrada contém varios casos de teste. A primeira linha contém um inteiro N indicando o numero de casos de teste. Cada uma das N linhas seguintes representa um caso de teste, contendo o nome de uma região composta por C caracteres (2 <= C <= 5000), o primeiro sempre será a letra 'm' e os seguintes serão 'p', 'q','r' ou 's'.

Saída

Para cada caso de teste na entrada seu programa deve produzir uma linha na saida, contendo os nomes das quatro regiões vizinhas da região dada na ordem de direção cima, baixo, esquerda, direita. Para os vizinhos que não mapeados vode deve imprimir '<none>' ao invés de seu nome. Deixe um espaço em branco entre dois nomes consecutivos.


Exemplo de entrada 2 mrspr mps

Exemplo de saída mrspq mrssq mrsps mrsqs mpp msp <none> mpr


Adicionado por:Wanderley Guimarăes
Data:2008-12-27
Tempo limite:0.391s
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:Final Sul-Americana da Maratona de Programação da ACM 2006

hide comments
2012-05-06 03:04:04 Victor Franco [ITA]
A primeira linha da entrada contém a indicaçăo da quantidade de casos de teste, o que é suficiente.
2010-10-19 04:23:46 Janio Carlos[GEDAL-UFT]
Como termina a entrada?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.