USACO 2017 January Silver Division, Cow Codes

Problem Statement

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 s, let F(s) be s 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 s, the cows build their infinite-length code string by repeatedly applying F; each step, therefore, doubles the length of the current string.

Given the initial string and an index N, please help the cows compute the character at the Nth position within the infinite code string.

INPUT FORMAT (file cowcode.in):

The input consists of a single line containing a string followed by N. The string consists of at most 30 uppercase characters, and N≤10^18. Note that NN may be too large to fit into a standard 32-bit integer, so you may want to use a 64-bit integer type (e.g., a "long long" in C/C++).

OUTPUT FORMAT (file cowcode.out):

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

COW 8 SAMPLE OUTPUT:

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

COW -> COWWCO -> COWWCOOCOWWC
                 12345678

The Algorithm

Let's observe the 2nd F() process: COWWCO -> COWWCOOCOWWC We notice that although location 7 maps to location 6, but locations 8 through 12 instead maps to 1 through 5. For notational convenience, let F(k0(s)=F(F(k−1)(s)), and define F(0)(s)=s We can compute the smallest k such that F(k)(s) contains the given index. If k=0, then we are looking at the original string and can, therefore, return the character directly. Otherwise, take F(k)(s) and split it into two halves. The desired index must be in the second half of F(k)(s). If it is the first character in the second half, then we want to return the last character in F(k−1)(s). Otherwise, due to the rotation, we decrease the index by 1 and return that character in F(k−1)(s). In the case where the index is 0, the index is reset to the maximal length.