In this HackerEarth AABBAAC problem solution, You are given an array S of N strings numbered from 0 to N-1. You build string sequence Ti by the following rules:
  1. T0 = S0
  2. Ti = Ti-1 + reverse(Ti-1) + Si
Now please answer M queries: by non-negative integer x output x-th character of the TN-1 in 0-based indexation. It's guaranteed that the x-th character of the TN-1 exists.


HackerEarth AABBAAC problem solution


HackerEarth AABBAAC problem solution.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <iomanip>
#include <string>
#include <string.h>
#include <cstdlib>
#include <bitset>
#include <cmath>
#include <random>

#define X first
#define Y second
#define mp make_pair
#define pb push_back

typedef long long ll;

using namespace std;

const int MAXN = 55;
int n, m;
string s[MAXN];

char rec(ll pos, int cur, ll len) {
    len -= s[cur].length();
    if (pos >= len) {
        return s[cur][pos - len];
    }
    len /= 2;
    if (pos >= len) {
        return rec(len + len - pos - 1, cur - 1, len);
    }
    else {
        return rec(pos, cur - 1, len);
    }
}

void solve() {
    cin>>n>>m;
    for (int i = 0; i < n; i++) {
        cin>>s[i];
    }
    for (int i = 0; i < m; i++) {
        ll len = 0, pos;
        cin>>pos;
        for (int j = 0; j < n; j++) {
            len *= 2;
            len += s[j].length();
            if (len > pos) {
                cout<<rec(pos, j, len);
                break;
            }
        }
    }
    cout<<"\n";
}

int main() {
    int test;
    cin>>test;
    while (test--) {
        solve();
    }
    return 0;
}


Second solution

#include <bits/stdc++.h>

using namespace std;

long long n,m,l[1000],x;
string st[1000];
long long tests;

int main(){

cin>>tests;
for (;tests;--tests)
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
     cin>>st[i];
    }
    
    for (int i=1;i<=n;i++)
     l[i]=l[i-1]*2+st[i].size();
    
    for (;m;--m)
    {
        cin>>x;
        for (int i=n;i;--i)
        {
            if (x>=2*l[i-1])
            {
             cout<<st[i][x-2*l[i-1]];
             break;
            }
            else if (x>=l[i-1])
             x=2*l[i-1]-x-1;
        }
    }
    cout<<endl;    
}

return 0;}