알파벳

시간 제한2초메모리 제한64 MB

요약
원형으로 놓인 토큰들에서 k칸씩 이동하며 다음 알파벳 토큰을 계속 삽입하는 과정을 시뮬레이션해서, m번째(최대 10억) 턴에 삽입되는 글자를 빠르게 구하는 문제입니다.
난이도

보통10점 중 6점

유형
연결 리스트, 시뮬레이션, 수학
정답자
아직 제출이 없습니다

문제

어린 소년 조니(Johnny)는 알파벳을 배우고 있습니다. 아버지는 생일 선물로 A부터 Z까지의 글자가 하나씩 적힌 토큰을 아주 많이 주었고, 조니는 알파벳을 익히려고 재미있는 게임을 만들었습니다.

먼저 조니는 토큰 몇 개를 골라 원형으로 늘어놓습니다. 그런 다음 시작할 토큰 하나를 정하고 수 kk를 하나 정합니다. 매 턴마다 조니는 현재 시작 토큰에서 출발해 원을 따라 앞으로 kk개의 토큰만큼 이동하여 당첨 토큰을 찾습니다(시작 토큰 자신은 세지 않습니다). 그리고 그 당첨 토큰 바로 뒤에 새 토큰 하나를 끼워 넣습니다. 새 토큰에는 당첨 토큰의 글자 다음에 오는 알파벳을 적습니다. 즉 A 다음은 B, B 다음은 C이며, 당첨 토큰이 Z이면 A를 끼워 넣습니다. 필요한 글자의 토큰은 항상 넉넉히 있습니다.

토큰을 끼워 넣은 뒤에는 방금 끼워 넣은 토큰에서 다음 턴을 시작합니다. 수 kk는 처음에 한 번만 정하며 턴이 바뀌어도 변하지 않습니다. 아래 그림은 처음 토큰이 J, O, H, N, N, Y(J가 시작 토큰)이고 k=3k = 3일 때의 처음 네 턴을 보여 줍니다.

Sample game figure

조니의 형 조지(Georgie)는 이미 학생이라 같은 게임을 머릿속으로 하며, 어느 턴에 끼워지는 글자든 알아맞혀 조니를 놀라게 합니다. 하지만 조니가 점점 많은 턴을 진행하면서 따라잡기 어려워지자, 조지는 답을 빠르게 찾는 프로그램을 만들기로 합니다.

입력

첫째 줄에 세 정수 nn, kk, mm이 주어집니다. nn은 처음에 원에 놓인 토큰의 수(1 ≤ n ≤ 10000), kk는 매 턴에 세는 토큰의 수(1 ≤ k ≤ 10000), mm은 턴의 수(1 ≤ m ≤ 10⁹)입니다.

둘째 줄에는 A부터 Z까지의 대문자 nn개로 이루어진 문자열이 주어집니다. 이는 처음에 원에 놓인 토큰을 시작 토큰부터 차례대로 나열한 것입니다.

출력

mm번째 턴에 끼워 넣는 토큰에 적힌 대문자 한 글자를 출력합니다.

예제4

  1. 예제 1

    입력
    6 3 4
    JOHNNY
    
    예상 출력
    Z
    
  2. 예제 2

    입력
    1 1 1
    A
    
    예상 출력
    B
    
  3. 예제 3

    입력
    1 4 3
    Q
    
    예상 출력
    R
    
  4. 예제 4

    입력
    10 4 1
    ABCDEFGHIJ
    
    예상 출력
    F