USACO 2017 January Contest Silver Division - Secret Cow Code

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can solve this problem by working the solution backwards. For each power of \(2\), split in half and make it the index of the first half. Repeat until you end up at the original string.

Source code

The source code in C++ can be seen below.

Solution 1

#include <bits/stdc++.h>
using namespace std;

string s;
long long n;

char solve(long long pos) {
    if (pos < s.size()) {
        return s[pos];
    }
    long long sz = s.size();
    while (sz * 2 <= pos) {
        sz *= 2;
    }
    if (sz == pos) {
        return solve(pos - 1);
    }
    else {
        return solve(pos - sz - 1);
    }
}
int main() {

    ifstream cin("cowcode.in");
    ofstream cout("cowcode.out");

    cin >> s >> n;
    cout << solve(n - 1);
    return 0;
}

Solution 2

#include <bits/stdc++.h>
using namespace std;

int N;
long long X, pow2[61];
string s;

int main() {

    ifstream cin("cowcode.in");
    ofstream cout("cowcode.out");

    pow2[0] = 1LL;
    for (int i = 1; i <= 60; i++) {
        pow2[i] = pow2[i-1]*2LL;
    }
    cin >> s >> X;
    N = (int) s.size();
    int depth = 0;
    for (int i = 0; i <= 60; i++) {
        if (N*pow2[i] >= X) {
            depth = i;
            break;
        }
    }
    while (depth > 0) {
        long long len = N*pow2[depth-1];
        if (X > len) {
            X = (X-len-1);
            if (X == 0) {
                X = len;
            }
        }
        depth--;
    }
    cout << s[X-1] << "\n";
    return 0;
}