### The Problem

The problem text is shown below (USACO Page):

### Explanation

I implemented a recursive algorithm for my solution: in order to find what character lies in index N after M duplications, my code looks back to the index in duplication M-1 that, after a right-shifted duplication, would end up in index N. The process repeats, stepping backwards until the original message is reached, and the character within the message that, after M duplications, would end up in index N is returned. The comments within my code explain more of the specifics.

### My Solution

``````import java.io.*;
import java.util.*;

public class SecretCowCode {
private static String fileNamePrefix = "cowcode";
private static String message;

public static void main(String[] args) throws IOException {

message = stringTokenizer.nextToken();
long desiredIndex = Long.parseLong(stringTokenizer.nextToken());

// Find the total length of the message after the right number of duplications for the desiredIndex to exist
// This length is the length of the message times the smallest power of 2 required to be >= desiredIndex
long lengthOfTotalMessage = message.length();

while (lengthOfTotalMessage < desiredIndex)
lengthOfTotalMessage *= 2;

// The problem counts characters starting from 1, but strings are 0-indexed
desiredIndex -= 1;

PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter(fileNamePrefix + ".out")));

// Begin recursion with the desired index and the length of the message
writer.println(charAt(desiredIndex, lengthOfTotalMessage));

writer.close();
}

private static char charAt(long index, long totalLength) {
// Base case: the original string has been reached (no more duplications to step back through)
if (index < message.length())
return message.charAt((int) index); // Can be casted to int because if this is true index is less than 30

// The totalLength is halved either way (the length of the string doubles with each duplication)
// The new index to check, however, may have to be recalculated, accounting for wrapping

if (index < totalLength / 2)
return charAt(index, totalLength / 2);
else
return charAt((index - 1) % (totalLength / 2), totalLength / 2);
}
}
``````

### Results

This solution successfully passes all test cases without exceeding the memory or runtime limits, as seen below: