다락방 timer 1s memory 128MB

루카는 자신의 다락방에서 새로운 게임을 생각해냈다. 다락방은 R행 C열의 칸으로 이뤄져 있으며, 각 행은 0부터 R-1로, 각 열은 0부터 C-1로 번호가 붙어있다.

루카는 다음과 같은 규칙을 통해 다락방의 각 칸을 색칠을 한다.

• 흰색 : 행과 열의 번호를 2진수로 나타냈을 때 적어도 한자리라도 동일한 자리에 1을 가질 경우 해당 칸을 흰색으로 칠한다. (4,5)의 경우 2진법으로 표현하면 (100, 101)이고 세 번째 자리가 모두 1이므로 흰색으로 칠해지게 된다.

• 회색 : 위의 경우에 해당 하지 않을 경우에 회색으로 칠한다. (2,5)의 경우 회색으로 칠해 진다.

루카가 기르는 고슴도치는 다락방을 특이한 방식으로 이동하게 되는데, 위쪽의 왼쪽 표와 같이 (0,0)에서 시작하여 지그-재그 형태로 이동을 하게 된다. 고슴도치가 이동을 하는 동안 루카는 고슴도치가 방문한 회색 칸의 개수를 세게 된다.

K개의 칸을 방문한 다음 고슴도치는 지쳐서 잠자리로 가게 되고, 루카는 방문한 회색칸을 모두 세었다는 기쁨을 간직하고 고슴도치와 마찬가지로 잠을 자러 가게 된다.

이런 게임을 몇 번 하던 루카는 굳이 고슴도치의 이동하는 것을 보고 있지 않아도 K개의 칸을 지그-재그 형태로 이동하였을 때 방문하게 되는 회색 칸의 개수를 셀 수 있다는 것을 알게 되었다.  또한 게임을 하는 칸의 수가 많고, K가 크더라도 빠른 시간 내에 이를 셀 수 있는 것을 알게 되었고, 친한 친구인 당신에게 이를 문제로 내었다. 머리를 짜내어 루카가 생각한 방법이 어떤 것인지 알아내고 이를 프로그램으로 구현해보자.