시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 256 MB 50 39 26 86.667%

문제

<그림> 무한 격자에서의 나이트의 경로

오른쪽과 위쪽으로 무한히 많이 뻗어 나가는 격자판이 있다. 이 격자에서 왼쪽에서 x번째, 아래에서 y번째 칸에는 수 $$\frac{(x+y-1)(x+y-2)}{2}+y$$가 쓰여 있다. 이 방법을 사용하면, 각 칸을 하나의 양의 정수에 일대일 대응시킬 수 있다.

여기서 나이트(체스의 기물 중 하나)는 격자판을 이동하려고 한다. 나이트는 두 칸 전진 후, 전진한 방향에서 오른쪽 혹은 왼쪽 중 한 방향으로 한 칸을 이동한다. 전진하는 방향은 위쪽, 아래쪽, 오른쪽 혹은 왼쪽 중 아무 방향이어도 상관없다. 하지만 격자판을 나가서는 안 된다. 즉, 나이트가 격자판 바깥으로 나가는 경우가 없다고 할 때 8칸 중 하나로 이동할 수 있다. 하지만 가장 왼쪽 아래에 있는 칸인 1번 칸에서는 8번 칸이나 9번 칸 중 하나로밖에 이동할 수 없다.

나이트는 1번 칸에서 시작해서 k번 이동하려고 한다. 이동하는 과정에서 나이트가 이동할 수 있는 칸이 여럿 있을 수 있다. 그러면 나이트는 한 번도 방문하지 않은 칸을 방문하려고 한다. 한 번도 방문하지 않은 칸이 여러 개일 경우에는 그중 쓰인 수가 제일 작은 칸으로 이동하고, 한 번도 방문하지 않은 칸이 없을 때는 더 이동하지 않고 멈춘다.

나이트가 k번 이동한 후에 위치한 칸의 번호를 찾는 프로그램을 작성하여라.

입력

나이트가 이동하는 횟수인 음이 아닌 정수 k가 첫째 줄에 주어진다. k가 0일 수 있음에 유의하여라.

나이트가 k번 이동하는 동안 멈추지 않으며, 그동안 방문한 칸에는 모두 231 미만의 정수가 쓰여 있는 k만 입력으로 주어짐이 보장된다.

출력

나이트가 k번 이동한 후에 위치한 칸의 번호를 출력하여라.

예제 입력 1

0

예제 출력 1

1

나이트가 0번 이동할 수 있음에 유의하여라.

예제 입력 2

100

예제 출력 2

84

출처