소 수학 천재들
면접 대비시간 제한1초메모리 제한16 MB
여섯 자리 수의 가운데 네 자리를 제곱하고 뒤의 여섯 자리만 남기는 과정을 반복합니다. 처음 반복되는 값, 순환 길이, 순환을 찾기까지의 횟수를 구합니다.
문제
농부 존은 소들이 수학 실력을 키우도록 돕는 것을 좋아한다. 그는 소들이 여러 수학 문제를 풀면 건초 맛 아이스크림을 주겠다고 약속했다.
그는 베시에게 말했다. "여섯 자리 정수를 하나 고르고, 그 수가 무엇인지 나에게 말해라. 그다음 가운데 네 자리를 뽑아라. 그 네 자리 수를 제곱한 뒤, 위쪽 자리를 버려서 여섯 자리 이하의 수가 될 때까지 줄여라. 결과를 나에게 말해라."
변장한 수학 천재 베시는 여섯 자리 수 655554를 골랐다. "Moo: 6 5 5 5 5 4"라고 말한 뒤, 가운데 네 자리 5555를 뽑아 제곱하여 30858025를 얻었다. 아래쪽 여섯 자리인 858025만 남기고 "Moo: 8 5 8 0 2 5"라고 FJ에게 답했다.
FJ는 베시의 계산 실력을 인정하며 고개를 끄덕였다. "이제 이미 나온 수가 다시 나올 때까지 같은 과정을 계속해라."
베시는 모든 과정을 한눈에 보기 위해 표를 만들기로 했다.
Middle Middle Shrunk to
Num 4 digits square 6 or fewer
655554 5555 30858025 858025
858025 5802 33663204 663204
663204 6320 39942400 942400
942400 4240 17977600 977600
977600 7760 60217600 217600 <-+
217600 1760 3097600 97600 |
97600 9760 95257600 257600 |
257600 5760 33177600 177600 |
177600 7760 60217600 217600 --+
베시가 표를 보여 주자 FJ는 웃으며 맛있는 건초 아이스크림을 큰 접시에 가득 내놓았다. "맞아요, 베시." 그가 칭찬했다. "이 수열은 네 개의 수로 이루어진 순환을 반복하고, 처음 만난 순환의 수는 217600이었다. 아홉 번째 반복에서 순환을 찾았다."
다른 소들도 아이스크림을 받도록 도와라. 여섯 자리 수가 주어지면, 순환을 찾을 때까지의 총 반복 횟수, 처음 만나는 순환의 수, 그리고 순환의 길이를 구하라.
FJ는 베시가 모든 요령을 알고 있는지 궁금했다. 그는 베시를 돕기 위해 표를 만들어 두었지만, 베시는 한 번도 묻지 않았다.
Middle Middle Shrunk to
Num 4 digits square 6 or fewer
200023 0002 4 4
4 0 0 0
0 0 0 0 [a self-loop]
이 경우의 결과는 순환을 찾기까지 세 번의 반복, 0에서 이루어지는 순환, 순환 길이 1이다.
참고: 프로그램은 16MB를 넘는 메모리를 사용할 수 없다.
입력
첫 줄에 수열 검사를 시작할 여섯 자리 정수 하나가 주어진다.
출력
첫 줄에 공백으로 구분된 정수 세 개를 출력한다. 순서대로 순환의 첫 번째 수, 순환의 길이, 순환을 검출하는 데 필요한 최소 반복 횟수이다.