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;}