1. Идея

Шифрование состояло из двух шагов:

1. исходную строку зашифровали шифром Цезаря со сдвигом k вперёд;
2. каждый символ результата записали как 8-битный ASCII-код, а все блоки склеили в одну длинную строку из 0 и 1.

Чтобы восстановить исходный текст, нужно сделать обратные действия в обратном порядке:

1. разбить двоичную строку на блоки по 8 бит;
2. каждый блок перевести в ASCII-символ;
3. для каждой заглавной буквы снять шифр Цезаря, то есть сдвинуть её на k назад.

Пробелы изменять не нужно.

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

Наблюдение 1. Длина кратна 8

По условию длина двоичной строки кратна 8, значит её можно однозначно разбить на байты.

Например, строка

010000010010000001011010

разбивается так:

• 01000001
• 00100000
• 01011010

Это ASCII-коды символов:

• A
• пробел
• Z

Наблюдение 2. Как перевести 8 бит в число

Блок вида 01011010 можно читать слева направо, постепенно накапливая число:

• текущий value = 0
• для каждого бита делаем value = value * 2 + bit

Так получается десятичное значение ASCII-кода.

Наблюдение 3. Цезарь нужно снимать только с букв

После ASCII-декодирования строка состоит только из заглавных латинских букв и пробелов.

Значит:

• если символ — буква от A до Z, делаем обратный сдвиг;
• если это пробел, оставляем как есть.

Наблюдение 4. Обратный сдвиг

Если буква была сдвинута вперёд на k, то для расшифровки надо сдвинуть её назад на k.

Удобно считать буквы числами от 0 до 25:

• A -> 0
• B -> 1
• ...
• Z -> 25

Тогда расшифровка делается так:

(позиция - k + 26) % 26

Добавление 26 нужно, чтобы не получить отрицательное число перед взятием остатка.

3. Алгоритм

1. Считать число k.
2. Считать двоичную строку s.
3. Создать пустую строку ответа.
4. Идти по строке s шагом 8.
5. Для каждого блока из 8 символов:
   • перевести его из двоичной записи в число value;
   • получить символ c с ASCII-кодом value;
   • если c — заглавная буква, заменить её на букву, сдвинутую назад на k;
   • добавить символ в ответ.
6. Вывести ответ.

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

Докажем, что алгоритм действительно восстанавливает исходный текст.

Пусть исходный текст состоял из символов t1, t2, ..., tn.

После шифра Цезаря каждая заглавная буква была заменена на букву, сдвинутую вперёд на k. Пробелы остались пробелами. Получилась строка c1, c2, ..., cn.

Затем каждый символ ci был записан своим 8-битным ASCII-кодом. Значит, входная двоичная строка состоит из подряд записанных кодов символов c1, c2, ..., cn.

Теперь рассмотрим действия алгоритма:

1. Он разбивает вход на блоки по 8 бит. Так как кодирование делалось именно блоками по 8 бит, каждый блок соответствует ровно одному символу ci.
2. Переводя каждый блок из двоичной записи в число, алгоритм получает ASCII-код символа ci.
3. Преобразование числа в символ даёт точно тот символ ci, который был после первого шага шифрования.
4. Если ci — заглавная буква, алгоритм сдвигает её на k назад. Это отменяет исходный сдвиг вперёд на k, поэтому получается исходная буква ti.
5. Если ci — пробел, он не меняется, и снова получается исходный символ ti.

Значит, после обработки всех блоков алгоритм восстанавливает все символы t1, t2, ..., tn, то есть весь исходный открытый текст.

5. Сложность

Пусть длина двоичной строки равна m.

Тогда:

• блоков будет m / 8;
• каждый блок обрабатывается за константное время, так как в нём ровно 8 бит.

Итоговая сложность:

• по времени: O(m)
• по памяти: O(m / 8) на строку ответа

6. Код на C++17

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

using namespace std;

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

    string result;
    result.reserve(s.size() / 8);

    for (size_t i = 0; i < s.size(); i += 8) {
        int value = 0;
        for (size_t j = i; j < i + 8; ++j) {
            value = value * 2 + (s[j] - '0');
        }

        char c = static_cast<char>(value);

        if (c >= 'A' && c <= 'Z') {
            int shifted = (c - 'A' - k + 26) % 26;
            c = static_cast<char>('A' + shifted);
        }

        result += c;
    }

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

7. Код на Python 3

k = int(input())
s = input().strip()

res = []

for i in range(0, len(s), 8):
    value = 0
    for j in range(i, i + 8):
        value = value * 2 + (ord(s[j]) - ord('0'))

    c = chr(value)

    if 'A' <= c <= 'Z':
        c = chr((ord(c) - ord('A') - k) % 26 + ord('A'))

    res.append(c)

print(''.join(res))