Informática – Nível Iniciante – Semana 38

por

Decimalmente Conectados

Problema inspirado em uma questão da Olimpíada de Matemática da Unicamp.

Salazar é um matemático famoso que foi classificado para a OMN (Olimpíada de Matemática da Nlogônia), uma competição extremamente perigosa. Querendo estudar seus adversários, ele entra no banco de dados da prova, porém o sistema é protegido com uma senha única para cada competidor. Felizmente existe um método de recuperação, onde você recebe um inteiro $$N$$ (10 ≤ $$N$$ ≤ 2×10⁹), e tem que devolver um par de inteiros $$X$$ e $$Y$$  (0 ≤ $$Y$$ ≤ $$X$$ ≤ 2×10⁹) tal que $$X$$ e $$Y$$ sejam decimalmente conectados e que sua soma seja igual a $$N$$.
Um par de inteiros é considerado decimalmente conectado caso ao apagar o dígito das unidades de um número, você consiga o outro número (por exemplo, 14 e 1 são decimalmente conectados).

Sabendo de suas habilidades de programação, Salazar pede sua ajuda para decifrar a senha de cada um dos $$T$$ competidores.

Restrições:

  • 10 ≤ $$N$$ ≤ 2×10⁹
  • 0 ≤ $$Y$$ ≤ $$X$$ ≤ 2×10⁹
  • 1 ≤ $$T$$ ≤ 10⁵
  • Para um conjunto de casos de teste valendo 20 pontos, $$N$$ ≤ 10⁴
  • Para um conjunto de casos de teste valendo 40 pontos, $$N$$ ≤ 10⁶
  • Para um conjunto de casos de teste valendo 40 pontos, sem restrições adicionais.

Entrada:

A primeira linha contém um inteiro $$T$$, que indica a quantidade de casos de teste. Em cada $$T$$ linha seguinte você recebe um número $$N$$.

Saída:

Você deve imprimir o resultado de cada caso de teste em uma única linha, com os inteiros $$X$$ e $$Y$$ nessa ordem, separados por um espaço. Também é possível que o sistema tenha gerado uma senha impossível, nesse caso imprima um único -1. É possível provar que só existe uma única resposta para cada caso de teste.

Exemplos:

Entrada Saída
3

15

10

777

14 1

-1

707 70

Para submeter sua solução use esse link