문제2100--수열

2100: 수열

실행시간 제한: 2 Sec  메모리사용 제한: 128 MB
제출: 64  통과: 11
[제출] [채점기록] [묻고답하기]

문제 설명

세준이는 가장 처음에 수 하나만 가지고 있는 수열을 가지고 있다. 매 초마다 1은 132로 바뀌고, 2는 211로 바뀌고, 3은 232로 바뀐다. 이런 변환은 매 초마다 동시에 일어난다. N초 후에 Left번째 수부터 Right번째 수 중에 1의 개수, 2의 개수, 3의 개수를 구하는 프로그램을 작성하시오. (Left와 Right를 셀 때, 가장 처음 수를 0번째 수, 그 다음 수를 1번째 수로 센다.)

예를 들어, 가장 처음 수가 1고, N=2이고, Left = 2, Right = 6이라고 하면, 2초 후에는 132232211이 될 것이다. 따라서 Left부터 Right까지 부분 수열은 22322이다. 따라서, 1의 개수는 0, 2의 개수는 4, 3의 개수는 1이다.

입력 설명

첫째 줄에 가장 처음에 들어있던 수가 주어진다. 이 수는 1, 2, 3중에 하나다. 둘째 줄에는 Left가 주어지고, 셋째 줄에는 Right, 넷째 줄에는 N이 주어진다. N은 0보다 크거나 같고, 20보다 작거나 같은 자연수이고, Right는 0보다 크거나 같으며, 3^N-1보다 작거나 같다. Left는 0보다 크거나 같고, Right보다 작거나 같고, Left와 Right는 모두 2147483647보다 작거나 같다.

출력 설명

첫째 줄에 1의 개수, 2의 개수, 3의 개수를 공백으로 구분하여 출력한다.

입력 예시 Copy

1
2
6
2

출력 예시 Copy

0 4 1

출처/분류