1. Идея

Нужно выполнить ровно те же два действия, что делает агент:

1. декодировать строку из стандартного Base64;
2. перевернуть получившийся текст.

Значит, задача сводится к аккуратной ручной реализации декодирования Base64, а затем к развороту строки.

Base64 кодирует данные блоками по 3 байта, превращая их в 4 символа. Поэтому входную строку удобно обрабатывать по 4 символа за раз.

2. Наблюдения

Как устроен Base64

В стандартном Base64 используется алфавит из 64 символов:

• A-Z дают значения от 0 до 25
• a-z дают значения от 26 до 51
• 0-9 дают значения от 52 до 61
• + даёт 62
• / даёт 63

Каждые 4 символа Base64 кодируют 24 бита, то есть 3 байта.

Если обозначить значения четырёх символов как a, b, c, d, то их можно собрать в одно число:

x = (a << 18) | (b << 12) | (c << 6) | d

После этого из x извлекаются три байта:

• первый: (x >> 16) & 255
• второй: (x >> 8) & 255
• третий: x & 255

Что делать с =

Символ = в Base64 означает добивку в конце строки.

Возможны случаи:

• без =: получаем 3 байта;
• один = в конце: получаем 2 байта;
• два = в конце: получаем 1 байт.

В эталонном решении для удобства = временно заменяется на 0, а затем просто не добавляются лишние байты:

• если третий символ равен =, второй байт не добавляем;
• если четвёртый символ равен =, третий байт не добавляем.

Почему потом достаточно просто перевернуть строку

По условию агент сначала декодирует текст, а потом читает его задом наперёд. Значит, после декодирования надо просто развернуть полученную строку.

3. Алгоритм

1. Считать строку s.
2. Построить таблицу соответствия символов Base64 их числовым значениям.
3. Завести пустую строку decoded.
4. Идти по строке s с шагом 4:
   • взять символы c1, c2, c3, c4;
   • перевести их в числа a, b, c, d, считая = как 0;
   • собрать 24-битное число x;
   • добавить первый байт;
   • если c3 != '=', добавить второй байт;
   • если c4 != '=', добавить третий байт.
5. Развернуть строку decoded.
6. Вывести результат.

4. Почему это работает

Рассмотрим один блок из 4 символов Base64.

Каждый такой символ кодирует 6 бит. Значит, 4 символа вместе содержат 24 бита информации. Именно эти 24 бита и собираются в число x:

• a занимает старшие 6 бит,
• b — следующие 6,
• c — ещё 6,
• d — последние 6.

После этого из x извлекаются три исходных байта, то есть ровно те данные, которые были закодированы в Base64.

Если в конце встречается =, это означает, что исходных байтов в последнем блоке было меньше трёх. Тогда алгоритм не добавляет лишние байты, поэтому результат декодирования получается точным.

Так как вся строка состоит из независимых блоков по 4 символа, декодирование каждого блока по отдельности восстанавливает всю исходную строку целиком.

Далее по условию нужно прочитать полученный текст в обратном порядке. Разворот строки делает именно это. Следовательно, алгоритм выводит правильный ответ.

5. Сложность

Пусть n — длина входной строки Base64.

• Построение таблицы занимает O(1).
• Обработка строки идёт по всем символам один раз, значит это O(n).
• Разворот строки тоже занимает O(n).

Итоговая сложность: O(n).

Дополнительная память: O(n) на декодированную строку.

6. Код на C++17

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    string s;
    cin >> s;

    vector<int> val(256, -1);
    for (int i = 0; i < 26; i++) {
        val['A' + i] = i;
        val['a' + i] = 26 + i;
    }
    for (int i = 0; i < 10; i++) {
        val['0' + i] = 52 + i;
    }
    val['+'] = 62;
    val['/'] = 63;

    string decoded;

    for (int i = 0; i < (int)s.size(); i += 4) {
        char c1 = s[i];
        char c2 = s[i + 1];
        char c3 = s[i + 2];
        char c4 = s[i + 3];

        int a = val[(unsigned char)c1];
        int b = val[(unsigned char)c2];
        int c = (c3 == '=') ? 0 : val[(unsigned char)c3];
        int d = (c4 == '=') ? 0 : val[(unsigned char)c4];

        int x = (a << 18) | (b << 12) | (c << 6) | d;

        decoded.push_back(char((x >> 16) & 255));
        if (c3 != '=') {
            decoded.push_back(char((x >> 8) & 255));
        }
        if (c4 != '=') {
            decoded.push_back(char(x & 255));
        }
    }

    reverse(decoded.begin(), decoded.end());
    cout << decoded << '\n';

    return 0;
}

7. Код на Python 3

s = input().strip()

val = {}
for i in range(26):
    val[chr(ord('A') + i)] = i
    val[chr(ord('a') + i)] = 26 + i
for i in range(10):
    val[chr(ord('0') + i)] = 52 + i
val['+'] = 62
val['/'] = 63

decoded = []

for i in range(0, len(s), 4):
    c1 = s[i]
    c2 = s[i + 1]
    c3 = s[i + 2]
    c4 = s[i + 3]

    a = val[c1]
    b = val[c2]
    c = 0 if c3 == '=' else val[c3]
    d = 0 if c4 == '=' else val[c4]

    x = (a << 18) | (b << 12) | (c << 6) | d

    decoded.append(chr((x >> 16) & 255))
    if c3 != '=':
        decoded.append(chr((x >> 8) & 255))
    if c4 != '=':
        decoded.append(chr(x & 255))

print(''.join(decoded)[::-1])