1. Идея

Нужно закодировать входную строку в стандартный Base64.

Base64 работает так:

• берём данные по 3 байта;
• эти 3 байта составляют 24 бита;
• разбиваем 24 бита на 4 группы по 6 бит;
• каждую группу используем как индекс в алфавите Base64.

Алфавит такой:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Если в конце строки осталось не 3 символа, а 1 или 2, недостающие байты считаются нулями, а в ответ добавляются символы =.

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

Наблюдение 1. Почему берут именно 3 символа

Один ASCII-символ занимает 1 байт, то есть 8 бит.

Три символа — это 3 * 8 = 24 бита.

Base64 кодирует данные кусками по 6 бит, значит из 24 бит получается ровно 4 числа:

• первые 6 бит,
• вторые 6 бит,
• третьи 6 бит,
• четвёртые 6 бит.

Каждое число находится в диапазоне от 0 до 63, поэтому его удобно использовать как индекс в строке из 64 символов Base64.

Наблюдение 2. Как собрать 3 байта в одно число

Пусть есть три байта:

• a
• b
• c

Тогда можно собрать их в одно 24-битное число:

x = (a << 16) | (b << 8) | c

После этого нужные 6-битные куски извлекаются так:

• (x >> 18) & 63
• (x >> 12) & 63
• (x >> 6) & 63
• x & 63

Здесь 63 — это двоичное число 111111, то есть маска для 6 бит.

Наблюдение 3. Что делать с концом строки

Есть три случая:

• осталось 3 символа — кодируем обычные 4 символа Base64;
• остался 2 символа — последний символ Base64 заменяется на =;
• остался 1 символ — два последних символа Base64 заменяются на ==.

Именно поэтому Base64-строка часто заканчивается символами =.

3. Алгоритм

1. Считываем всю строку целиком через getline в C++ или input() в Python.
2. Запоминаем строку-алфавит Base64.
3. Идём по входной строке с шагом 3.
4. Для каждой позиции:
   • берём текущий символ a;
   • если есть второй символ, берём b, иначе 0;
   • если есть третий символ, берём c, иначе 0;
   • собираем число x = (a << 16) | (b << 8) | c;
   • добавляем в ответ:
     • символ по индексу (x >> 18) & 63,
     • символ по индексу (x >> 12) & 63,
     • если второй символ существовал, символ по индексу (x >> 6) & 63, иначе =,
     • если третий символ существовал, символ по индексу x & 63, иначе =.
5. Выводим ответ.

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

Рассмотрим очередную группу не более чем из трёх символов.

Случай 1. Есть 3 символа

Пусть их байты равны a, b, c.

После выражения

x = (a << 16) | (b << 8) | c

в числе x подряд записаны все 24 бита этих трёх байтов.

Теперь:

• (x >> 18) & 63 берёт первые 6 бит;
• (x >> 12) & 63 берёт следующие 6 бит;
• (x >> 6) & 63 берёт ещё 6 бит;
• x & 63 берёт последние 6 бит.

Это в точности и есть стандартное преобразование Base64, значит четыре полученных индекса корректно переводятся в четыре символа алфавита.

Случай 2. Есть 2 символа

Третий байт заменяется на 0.

Тогда первые 18 значимых бит задаются реальными данными, и:

• первые два символа Base64 определяются полностью;
• третий символ Base64 тоже вычисляется корректно, потому что использует оставшиеся данные и добавленные нули;
• четвёртый символ не должен кодировать несуществующие данные, поэтому вместо него ставится =.

Это соответствует стандарту Base64.

Случай 3. Есть 1 символ

Второй и третий байты заменяются на 0.

Тогда:

• первые два символа Base64 вычисляются по данным и добавленным нулям;
• третьего и четвёртого реальных 6-битных блоков из исходных данных уже нет, поэтому они заменяются на =.

Это тоже ровно стандартное правило Base64.

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

5. Сложность

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

• Время работы: O(n), потому что каждый символ обрабатывается один раз.
• Дополнительная память: O(n) на строку ответа.

6. Код на C++17

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    getline(cin, s);

    string base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    string ans;

    int n = (int)s.size();
    for (int i = 0; i < n; i += 3) {
        int rem = n - i;

        unsigned char a = s[i];
        unsigned char b = (rem > 1 ? (unsigned char)s[i + 1] : 0);
        unsigned char c = (rem > 2 ? (unsigned char)s[i + 2] : 0);

        int x = (a << 16) | (b << 8) | c;

        ans += base64[(x >> 18) & 63];
        ans += base64[(x >> 12) & 63];

        if (rem > 1) {
            ans += base64[(x >> 6) & 63];
        } else {
            ans += '=';
        }

        if (rem > 2) {
            ans += base64[x & 63];
        } else {
            ans += '=';
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

s = input()

base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
ans = []

n = len(s)
for i in range(0, n, 3):
    rem = n - i

    a = ord(s[i])
    b = ord(s[i + 1]) if rem > 1 else 0
    c = ord(s[i + 2]) if rem > 2 else 0

    x = (a << 16) | (b << 8) | c

    ans.append(base64[(x >> 18) & 63])
    ans.append(base64[(x >> 12) & 63])

    if rem > 1:
        ans.append(base64[(x >> 6) & 63])
    else:
        ans.append('=')

    if rem > 2:
        ans.append(base64[x & 63])
    else:
        ans.append('=')

print("".join(ans))