양방향 코드

지구와 위성 사이의 우주 통신에서는 4G 같은 휴대폰 통신처럼 메시지를 그냥 보낼 수 없다. 신호가 이동하는 거리가 매우 길어서 잡음 때문에 메시지가 손상될 수 있기 때문이다.

연구자들은 오랜 시간에 걸쳐 이 문제를 우회할 방법을 찾았고, 그 해답은 중복 데이터를 넣는 데 있었다. 그러면 수신자는 받은 데이터에 오류가 있는지 검사할 수 있고, 오류가 있으면 송신자에게 메시지를 다시 보내 달라고 요청하거나, 오류가 작을 경우 원래 메시지를 복구할 수도 있다. 이 연구 분야를 부호 이론이라고 한다.

우리는 실수를 막기 위해 새로운 중복 시스템을 만들었다. 이제 어떤 수를 보내려면 그 수를 회문수의 합으로 표현하는 방법을 찾아 각 회문수를 평소처럼 보내면 된다. 그러면 수신자는 받은 수가 회문수가 아닌지 검사할 수 있고, 그런 경우 오류가 발생했음을 알 수 있다.

통신을 충분히 효율적으로 유지하기 위해 연구소는 수를 많아야 $10$개의 회문수의 합으로만 분해할 수 있다는 제약을 추가했다. 모든 수를 회문수들의 합으로 분해하는 방법을 찾아야 한다.

최근 논문은 모든 양의 정수가 세 회문수의 합이라는 사실을 보였다.

• 한 줄에 정수 $n$ ($1\leq n < 10^{18}$)이 주어진다. 이 수를 회문수의 합으로 나타내야 한다.

먼저 필요한 회문수의 개수 $1\leq k\leq 10$을 한 줄에 출력한다. 그다음 $k$개의 줄에 각각 회문수를 하나씩 출력한다.