Narukvice

U fabrici ASCII narukvica, postoje dve mašine. Prva mašina uzima narukvicu, pravi njenu kopiju i nadovezuje je na početnu narukvicu. Druga mašina uzima narukvicu, pravi narukvicu koja predstavlja sliku u ogledalu početne narukvice i nadovezuje je na početnu narukvicu.

Ukoliko je poznato kako je izgledala početna narukvica, kao i kojim redom je prosleđivana mašinama, napisati program koji proverava koji karakter se nalazi na \(k\)-toj poziciji narukvice nakon \(n\) modifikacija.

Opis ulaza

Sa standardnog ulaza se učitavaju \(n\) (\(1 \leq n \leq 20\)), \(k\) (\(0 \leq k < |s| 2^n\)) i \(s\) (\(2 \leq |s| \leq 3\)), pri čemu je \(s\) početna narukvica. Nakon toga se učitava \(n\) modifikacija. Ukoliko je unesen karakter \(k\), primenjena je prva mašina (kopija), a ukoliko je unesen karakter \(o\), primenjena je druga mašina (kopija u ogledalu).

Opis izlaza

Ispisati karakter koji se nalazi na \(k\)-toj poziciji u narukvici nakon svih modifikacija. Pozicije se broje od 0.

Primer 1

Ulaz

3 13 ab
k k o

Izlaz

a

Objašnjenje

Narukvica nakon modifikacija izgleda ovako: ababababbabababa

Primer 2

Ulaz

3 6 ab
o k k

Izlaz

b

Objašnjenje

Narukvica nakon modifikacija izgleda ovako: abbaabbaabbaabba

Rešenje

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

/* k = 13
 * s = ab
 * n = 3: k k o
 * init: ab                     l=2=s.size()
 *    k: abab                   l=4=s.size() * 2
 *         k l
 *         m
 *    k: abababab               l=8=s.size() * 2^2
 *         k m   l
 *    o: ababababbabababa       l=16=s.size() * 2^3
 *       0   k' |m    k  l
 *             m-1
 *
 *  op o:
 *       m - 1 - k' = k - m
 *       k' = 2*m - k - 1
 *
 *  op k:
 *       k' - 0 = k - m
 *       k' = k - m
 */     

char kth_char(vector<char> &ops, int n, int k, int l, string &s)
{
    if (n == 0) {
        return s[k];
    }

    int m = l / 2;

    if (k < m) {
        return kth_char(ops, n - 1, k, m, s);
    }

    if (ops[n - 1] == 'k') {
        return kth_char(ops, n - 1, k - m, m, s);
    } else { // ops[i] == 'o'
        return kth_char(ops, n - 1, 2 * m - k - 1, m, s);
    }

}

int main() 
{
    int n, k;
    string s;

    cin >> n >> k >> s;

    vector<char> ops(n);
    for(int i = 0; i < n; i++) {
        cin >> ops[i];
    }

    int l = s.size() * pow(2, n);
    cout << kth_char(ops, n, k, l, s) << endl;

    return 0;
}