Sabias que o número de telemóveis existentes no mundo ultrapassa já a metade do número de seres humanos que nele habitam? São mais de 3,3 mil mlhões de telemóveis! Claro que isto não quer dizer que metade dos habitantes do nosso planeta tem telemóvel. É que muitas pessoas têm dois, três ou mais. De facto, estima-se que em cerca de 60 países o número de telemóveis existentes é superior à sua própria população. O telemóvel mudou definitivamente a nossas vidas...
A propósito de telemóveis, certamente já reparaste na rapidez com que os jovens escrevem no teclado de um telemóvel. Sejam palavras ou números, tudo é digitado com uma rapidez assombrosa. Concentremo-nos agora nos números. Será que todos se prestam a serem escritos com a mesma rapidez? Comecemos por analisar um teclado clássico de um telemóvel, que pode ser visto na figura seguinte:
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
| * | 0 | # |
O número 23698, por exemplo, é fácil de escrever, uma vez que os vários dígitos consecutivos são adjacentes no teclado. Vamos concretizar melhor esta definição, dizendo que um número é "fácil de escrever" se um par de dígitos adjacentes no próprio número é constituído pelo mesmo dígito ou por dígitos adjacentes (vertical ou horizontalmente) no teclado clássico do telemóvel. Por exemplo, 1225 é um número "fácil de escrever" uma vez que 1 e 2 são adjacentes no teclado, 2 e 2 são o mesmo dígito e finalmente 2 e 5 são adjacentes. Já 126 não é "fácil de escrever" uma vez que 2 e 6 não são adjacentes pela definição dada.
Se pensarmos na sequência crescente de números "fáceis de escrever", chegamos ao seguinte:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 21, 22, 23, 25, 32, 33, 36, 41, 44, 45, 47, ...
Se associarmos números de ordem à sequência, podemos por exemplo dizer que o 3 é o quarto número da sequência, ou que 36 é o vigésimo número. Por outras palavras o número de ordem 4 na sequência é 3; o número de ordem 20 é 36.
Ordem: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ... --------------------------------------------------------------------------------------------- Número: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 21, 22, 23, 25, 32, 33, 36, 41, 44, 45, 47, ...
Dado um número de ordem, serás capaz de descobrir qual o número da sequência a que corresponde?
Escreve um programa que dado um número de ordem, calcula qual o número da sequência crescente de números "fáceis de escrever" que tem esse número de ordem. Um número é "fácil de escrever" se todos os seus dígitos consecutivos são iguais ou adjacentes (vertical ou horizontalmente) no teclado do telemóvel.
Na primeira linha de input vem um número inteiro C indicando o número de casos a considerar (1 ≤ C ≤ 500).
Seguem-se exactamente C linhas, cada uma delas contendo um número de ordem N da sequência (1 ≤ N ≤ 150 000). Estes números podem vir por qualquer ordem.
O output é constituído por exactamente C linhas, cada uma no formato "N: Fn", onde N é o número de ordem e Fn é o N-ésimo número da sequência crescente de números "fáceis de escrever". As linhas devem vir na mesma ordem do input.
5 4 20 1 23 30
4: 3 20: 36 1: 0 23: 45 30: 63