종과 북
문제
어느 공방의 장인은 번호가 붙은 작업 지시를 받아 일한다. 지시의 번호는 0 이상의 정수이며, 장인은 지시를 하나 받으면 번호에 따라 다음과 같이 움직인다.
1) 0번 지시를 받으면 종을 한 번 치고 그 지시를 끝낸다.
2) 1번 지시를 받으면 북을 한 번 치고 그 지시를 끝낸다.
3) 2번 이상인 K번 지시를 받으면, 먼저 K-1번 지시를 받은 것처럼 끝까지 수행하고, 이어서 K-2번 지시를 받은 것처럼 끝까지 수행한다. 이 경우에 장인은 종도 북도 직접 치지 않는다.
공방의 주인은 N번 지시를 한 번 내렸을 때 종이 몇 번 울리고 북이 몇 번 울리는지 알고 싶다. 주인은 이것을 T번 묻는다.
결과적으로 지시의 번호 N이 주어졌을 때, 종이 울리는 횟수와 북이 울리는 횟수를 차례대로 구하는 프로그램을 작성하여라.
예를 들어 N=3번 지시를 한 번 내렸다고 해보자. 3번 지시는 2번 지시와 1번 지시를 차례로 불러오고, 그 가운데 2번 지시는 다시 1번 지시와 0번 지시를 차례로 불러온다. 장인이 움직인 차례를 적으면 다음과 같다.
| 차례 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 수행한 지시 | 3번 | 2번 | 1번 | 0번 | 1번 |
| 울린 것 | 북 | 종 | 북 |
종은 한 번, 북은 두 번 울렸다. 따라서 이 경우 정답은 1과 2다.
지시의 번호를 0부터 5까지 올려 가며 같은 방식으로 세면 다음과 같다.
| N | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 종이 울린 횟수 | 1 | 0 | 1 | 1 | 2 | 3 |
| 북이 울린 횟수 | 0 | 1 | 1 | 2 | 3 | 5 |
0번 지시와 1번 지시는 그 자리에서 한 번만 울리고 끝나므로 각각 1과 0, 0과 1이다. 그 위의 번호는 바로 아래 두 번호의 횟수를 그대로 더한 값이 된다.
입출력 예시
예시 1
입력
3 0 1 3
출력
1 0 0 1 1 2
예시 2
입력
2 39 40
출력
39088169 63245986 63245986 102334155
예시 3
입력
1 0
출력
1 0
입력 조건
가장 먼저 주인이 묻는 횟수 T가 자연수로 주어진다. (T는 41보다 작거나 같은 자연수다.)
이어서 T개의 줄에 걸쳐 각 번에 내리는 지시의 번호 N이 한 줄에 하나씩 차례대로 주어진다. (N은 0 이상 40 이하의 정수다.) N이 0이거나 1인 경우도 주어진다.
출력 조건
T개의 줄에 걸쳐, 각 지시마다 종이 울린 횟수와 북이 울린 횟수를 이 순서대로 공백 하나로 구분해 한 줄에 출력한다. 북이 울린 횟수 뒤에는 공백을 붙이지 않고 줄을 바꾼다.
요구사항
- 0번 지시는 종만 한 번, 1번 지시는 북만 한 번 울립니다
- 2번 이상의 지시는 스스로 종이나 북을 치지 않고 아래 두 번호의 지시를 차례로 불러옵니다
- 같은 번호의 지시가 여러 번 불려 오면 그 횟수도 모두 셉니다
- N이 40일 때까지 세야 하므로, 미리 작은 번호부터 횟수를 쌓아 두고 쓰면 됩니다
- 한 줄에 두 수를 공백 하나로 구분해 출력하며 종이 먼저입니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
3 0 1 3
1 0 0 1 1 2
1 0
1 0
2 39 40
39088169 63245986 63245986 102334155
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.