Page not loading? Try clicking here.
Placeholder

#2142

[초등부] 2024 KOI 1차대회 대비 모의고사 (2주차)

대나무 게임 (Bamboo Game) 1s 128MB

Problems

쌍둥이 판다 루이와 후이는 푸바오에게서 N개의 대나무를 받았다.

루이와 후이는 서로 더 많은 대나무를 먹기위해 대나무 게임을 시작하였다.

대나무 게임의 규칙은 다음과 같다.

  1. 루이가 대나무를 두 그룹으로 나누는데, 개수 차이가 0 또는 1이 되게 한다. 이 때, 대나무가 0개인 그룹이 존재할 수 있다.

  2. 후이가 두 그룹 중 더 대나무가 많은 그룹을 선택하여 대나무를 다 먹는다.

  3. 이번엔 후이가 대나무를 두 그룹으로 나눈다.

  4. 이번엔 루이가 더 대나무가 많은 그룹의 대나무를 다 먹는다.

  5. 위 1~4를 반복한다.

N개의 대나무가 다 먹혀 사라지는 동안 대나무 게임은 계속되었고, 결과적으로 루이는 A개의 대나무를, 후이는 B개의 대나무를 먹었다.


Input

첫 줄에 대나무의 개수 N이 입력된다. (0 \le N \le 2^{31}-1)


Output

첫 줄에 A와 B를 공백으로 나누어 출력한다.


Example #1

10
4 6

루이가 10개의 대나무를 5개, 5개로 나누고 후이가 5개를 먹는다.

후이가 5개의 대나무를 3개, 2개로 나누고 루이가 3개를 먹는다.

루이가 대나무 2개를 1개, 1개로 나누고 후이가 1개를 먹는다.

후이가 대나무 1개를 1개, 0개로 나누고 루이가 1개를 먹는다.


Example #2

0
0 0

Example #3

1
0 1

Example #4

2
1 1

Example #5

21
6 15
You must sign in to write code.