7309 : 재귀 문자열 치환
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
초기 문자열과 치환 규칙이 주어질 때, 규칙을 $N$번 재귀적으로 적용한 후 최종 문자열의 길이와 특정 위치의 문자를 출력하십시오.
규칙이 기하급수적으로 문자열을 늘릴 수 있으므로 실제 문자열을 저장하지 않고 재귀적으로 특정 위치를 추적하는 방식이 효율적입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
규칙이 기하급수적으로 문자열을 늘릴 수 있으므로 실제 문자열을 저장하지 않고 재귀적으로 특정 위치를 추적하는 방식이 효율적입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 초기 문자열과 규칙 수 $K$가 주어집니다.
이어서 $K$개의 줄에 치환 규칙
마지막 줄에 반복 횟수 $N$과 확인할 위치 $P$(1-based)가 주어집니다.
이어서 $K$개의 줄에 치환 규칙
원래문자 치환후문자열이 주어집니다.마지막 줄에 반복 횟수 $N$과 확인할 위치 $P$(1-based)가 주어집니다.
출력 설명
$N$번 적용 후의 최종 문자열 길이와 $P$번째 문자를 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
A 2
A AB
B A
3 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5 B도움
각 규칙을 $N$번 반복하며 문자열을 확장합니다. 문자열이 너무 길어지면 길이만 추적하고, 특정 위치 $P$의 문자는 역추적으로 구합니다.