#PU692. USACO 2017 January Contest, Silver — Problem 3. Secret Cow Code

    ID: 1463 传统题 文件IO:cowcode 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:jan17来源:usaco.orgscoring:equal_test_cases模拟字符串

USACO 2017 January Contest, Silver — Problem 3. Secret Cow Code

USACO 2017 January Contest, Silver — Problem 3. Secret Cow Code

题目描述

The cows are experimenting with secret codes, and have devised a method for creating an infinite-length string to be used as part of one of their codes. Given a string ss, let F(s)F(s) be ss followed by ss "rotated" one character to the right (in a right rotation, the last character of ss rotates around and becomes the new first character). Given an initial string ss, the cows build their infinite-length code string by repeatedly applying FF; each step therefore doubles the length of the current string. Given the initial string and an index NN, please help the cows compute the character at the NNth position within the infinite code string.

输入格式

The input consists of a single line containing a string followed by NN. The string consists of at most 30 uppercase characters, and N≤1018N \leq 10^{18}.

输出格式

Please output the NNth character of the infinite code built from the initial string. The first character is N=1N=1.

数据范围

(见题面原文)

样例

样例 1

COW 8
C
In this example, the initial string COW expands as follows:
COW -> COWWCO -> COWWCOOCOWWC
                 12345678
Problem credits: Brian Dean

提示

want to use a 64-bit integer type (e.g., a "long long" in C/C++).