RiseOJ – 비밀 소 암호

설명

소들은 비밀 암호를 실험하고 있으며, 암호의 일부로 사용할 무한 길이 문자열을 만드는 방법을 고안해 냈다.

문자열 $$s$$ 가 주어질 때, $$F(s)$$ 를 $$s$$ 뒤에 $$s$$ 를 오른쪽으로 한 문자 "회전"한 것을 이어 붙인 문자열이라 하자(오른쪽 회전에서는 $$s$$ 의 마지막 문자가 돌아 나와 새로운 첫 문자가 된다). 초기 문자열 $$s$$ 가 주어지면, 소들은 $$F$$ 를 반복해서 적용하여 무한 길이의 암호 문자열을 만든다. 즉, 한 단계를 거칠 때마다 현재 문자열의 길이가 두 배가 된다.

초기 문자열과 인덱스 $$N$$ 이 주어질 때, 무한 암호 문자열의 $$N$$ 번째 위치에 있는 문자를 계산해 소들을 도와주자.

문제 출제: 브라이언 딘(Brian Dean)

제약

문제 출제: 브라이언 딘(Brian Dean)

입력 형식

입력은 문자열과 그 뒤에 오는 $$N$$ 으로 이루어진 한 줄이다. 문자열은 최대 30개의 대문자로 이루어지며, $N \leq 10^{18}$ 이다.

$$N$$ 은 표준 32비트 정수에 담기에는 너무 클 수 있으므로, 64비트 정수형(예: C/C++의 "long long")을 사용하는 것이 좋다.

출력 형식

초기 문자열로부터 만들어진 무한 암호 문자열의 $$N$$ 번째 문자를 출력한다. 첫 번째 문자가 $$N=1$$ 이다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 cowcode.in · 출력을 쓸 파일 cowcode.out

예제 1

입력

COW 8

출력

설명

In this example, the initial string COW expands as follows:

COW -> COWWCO -> COWWCOOCOWWC
                 12345678

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > January > Silver

올림피아드 > USACO > 2016-2017 > January > Silver

태그

JudgeUSACO

비밀 소 암호

평가 및 의견

풀이 제출