DNK duplikator

U laboratoriji se generiše lanac DNK nad alfabetom \(\{ A, C, G, T \}\). Nad trenutnim lancom \(X\) primenjuje se \(n\) operacija. Postoje dve operacije:

• K — operacija kopije: \(X' \leftarrow X \circ X\)
• C — operacija komplementa: \(X' \leftarrow X \circ \mathsf{comp(X)}\)

Ovde je \(\mathsf{comp}(\cdot)\) komplementiranje po standardnim parovima: \(A \leftrightarrow T\), \(C \leftrightarrow G\), a operator \(\circ\) označava nadovezivanje nizova.

Za početni lanac \(s\) i \(n\) operacija odrediti koji se nukleotid nalazi na \(k\)-toj poziciji nakon što su sve operacije primenjene. Pozicije se broje od 0.

Opis ulaza

Sa standardnog ulaza učitava se broj operacija \(n\) (\(1 \leq n \leq 60\)), tražena pozicija \(k\) (\(0 \leq k < |s| \cdot 2^n \leq 10^9\)), i početni DNK lanac \(s\) (\(1 \leq |s| \leq 2 \cdot 10^5\)), karakteri su iz skupa \(\{ A, C, G, T \}\)).

U sledećem redu nalazi se \(n\) operacija, karaktera razdvojenih razmacima, K ili C.

Opis izlaza

Ispisati jedan karakter iz skupa \(\{ A, C, G, T \}\) — sadržaj na \(k\)-toj poziciji nakon svih operacija.

Primer 1

Ulaz

3 13 AT
K C K

Izlaz

A

Objašnjenje

Kada primenimo, redom, operacije K, C i K na dnk lanac AT dobijamo lanac ATATTATAATATTATA.

Primer 2

Ulaz

2 9 CGA
C C

Izlaz

C

Objašnjenje

Kada primenimo operaciju C dva puta na dnk lanac CGA, dobijamo lanac CGAGCTGCTCGA.

Rešenje

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

using namespace std;

inline char comp(char c)
{
    switch (c) {
        case 'A':
            return 'T';
        case 'T':
            return 'A';
        case 'C':
            return 'G';
        case 'G':
            return 'C';
        default:
            return c;
    }
}

char kth_char(const string &s, const vector<char> &op, 
              const int i, const int k, const int L, bool is_comp)
{
    if (i == -1) {
        return is_comp ? comp(s[k]) : s[k];
    }

    int new_L = L / 2;
    
    if (k < new_L) {
        return kth_char(s, op, i - 1, k, new_L, is_comp);
    }

    is_comp = op[i] == 'C' ? !is_comp : is_comp;
    return kth_char(s, op, i - 1, k - new_L, new_L, is_comp);
}

int main() 
{
    int n, k; cin >> n >> k;

    string s; cin >> 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(s, ops, n - 1, k, L, false) << endl;

    return 0;
}