XYZ 문자열
시간 제한2초메모리 제한128 MB
X, Y, Z 문자를 규칙에 따라 반복 치환해 만든 N단계 문자열에서 길이, k번째 문자, 특정 문자 개수를 문자열을 직접 만들지 않고 구합니다.
문제
"XYZ 문자열"은 문자 X, Y, Z로만 이루어지며, 다음 규칙으로 단계별로 만들어지는 문자열이다.
- 1단계 문자열은
X이다. - 다음 단계의 문자열은 바로 이전 단계 문자열의 각 문자를 아래 규칙대로 동시에 바꾸어 만든다.
X는YZ가 된다.Y는Z가 된다.Z는X가 된다.
처음 여섯 단계는 다음과 같다.
XYZZXXYZYZZXZXXYZ
N단계의 XYZ 문자열에 대해 다음 세 질의 중 하나를 처리하는 프로그램을 작성하시오.
- N단계 문자열의 길이를 구한다.
- N단계 문자열의 k번째 문자를 구한다.
- N단계 문자열에서 주어진 문자
X,Y,Z중 하나가 몇 번 나타나는지 구한다.
입력
첫째 줄에 질의 번호가 주어진다. 질의 번호는 1, 2, 3 중 하나이다.
둘째 줄에 정수 N (1 <= N <= 100)이 주어진다.
질의 번호가 2이면 셋째 줄에 정수 k가 주어진다. k는 항상 N단계 문자열의 길이 이하이다.
질의 번호가 3이면 셋째 줄에 문자 X, Y, Z 중 하나가 주어진다.
출력
질의 번호가 1이면 문자열의 길이를 출력한다.
질의 번호가 2이면 k번째 문자를 출력한다.
질의 번호가 3이면 주어진 문자가 나타나는 횟수를 출력한다.