Diamonds Are for Evers
면접 대비시간 제한1초메모리 제한512 MB
정사각형 격자에 중첩된 마름모 대각선을 따라 쓴 메시지를, 모든 칸을 행 순서로 이어 붙인 문자열에서 복원한다.
문제
최고의 비밀 요원 Claude L. Evers는 암호 메시지를 보내는 독특한 방법을 쓴다. 메시지는 정사각형 글자 격자에 다음과 같이 심어진다. 격자의 가장 왼쪽 변 가운데 글자에서 시작해 격자 위쪽을 향하는 대각선을 따라 메시지를 쓴다. 위쪽에 닿으면 오른쪽을 향하는 대각선으로 메시지를 이어 가다가 오른쪽 변에 닿는다. 이런 식으로 계속해서 왼쪽 변에 다시 닿을 때까지 마름모를 그린다. 그러면 방금 채운 마름모 안에 중첩된 마름모로 메시지를 이어 쓰고, 그다음 안쪽 마름모, 또 그다음 안쪽 마름모 순으로 계속한다. 원래 마름모의 안쪽과 바깥쪽에 남는 칸은 모두 무작위 글자로 채운다.
아래 격자들은 메시지 GENERAL TSO NEEDS CHICKEN NOW를 부호화하는 단계를 보여 준다. 첫 번째 격자는 첫 마름모를 다 채운 뒤의 상태다. 두 번째, 세 번째, 네 번째 격자는 점점 작아지는 마름모를 채운 상태를 보여 준다. 마지막 격자는 격자 둘레의 빈 칸에 무작위 글자를 넣은 최종 메시지다.
원래 메시지가 마름모 집합 전체를 채우지 못했다면 그 빈 자리도 무작위 글자로 채워진다(GENERAL TSO HATES CHICKEN을 부호화한 Sample Input 2가 그 예이다). 메시지를 보낼 때 Evers는 모든 행을 위에서 아래로 이어 붙인다. 위 격자는 다음과 같이 전송된다.
THEESEARENSRNTAEDNCACGEEWNHLTEKOITUALNCSLYRANODOM
그런데 Evers는 치명적인 실수를 하나 저질렀다. 그가 우리에게 부호화 방법을 설명해 버린 것이다! 이제 우리는 그가 보내는 메시지를 해독하는 프로그램을 작성할 수 있다. 물론 여기서 "우리"는 여러분을 뜻한다.
입력
입력은 대문자 알파벳으로 이루어진 문자열 하나다. 각 문자열의 길이는 홀수 정수의 제곱이고 1,000보다 작다.
출력
해독한 메시지를 출력한다. 원래 메시지가 마름모 집합 전체를 채우지 못했다면 이 메시지 끝에 무작위 글자가 몇 개 붙어 있을 수 있다.