1. Идея

Сообщение было зашифровано в два шага:

1. к исходному тексту применили шифр Цезаря со сдвигом k вперёд;
2. результат закодировали в Base64.

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

1. сначала декодировать строку из Base64;
2. потом для каждой заглавной буквы выполнить сдвиг Цезаря назад на k.

Именно это и делает решение.

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

Наблюдение 1. Порядок снятия защиты важен

Так как сначала был применён Цезарь, а потом Base64, расшифровывать нужно наоборот:

• сначала Base64;
• затем обратный сдвиг по алфавиту.

Если попытаться сначала сдвигать символы в Base64-строке, получится бессмысленный результат.

Наблюдение 2. После Base64 получаются только заглавные буквы и пробелы

По условию после декодирования Base64 строка состоит только из:

• символов 'A'–'Z';
• пробелов.

Значит:

• пробелы менять не нужно;
• для букв достаточно сделать обычный циклический сдвиг назад по алфавиту.

Например, если k = 1:

• 'B' -> 'A'
• 'A' -> 'Z'

Наблюдение 3. Как устроено декодирование Base64

В Base64 каждые 4 символа кодируют до 3 байт данных.

Для каждого символа Base64 есть значение от 0 до 63:

• 'A'–'Z' -> 0–25
• 'a'–'z' -> 26–51
• '0'–'9' -> 52–61
• '+' -> 62
• '/' -> 63

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

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

Из него извлекаются три байта:

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

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

3. Алгоритм

1. Считать k.
2. Считать строку s в Base64.
3. Построить таблицу соответствия символов Base64 их значениям от 0 до 63.
4. Обрабатывать строку s блоками по 4 символа:
   • получить значения a, b, c, d;
   • если третий или четвёртый символ равен '=', использовать 0;
   • собрать 24-битное число triple;
   • извлечь из него байты и добавить в декодированную строку:
     • первый байт всегда;
     • второй, если третий символ не '=';
     • третий, если четвёртый символ не '='.
5. Пройти по декодированной строке:
   • если символ — заглавная буква, заменить его на букву со сдвигом назад на k;
   • иначе оставить как есть.
6. Вывести ответ.

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

Докажем по шагам.

Шаг 1. Декодирование Base64 восстанавливает строку после шифра Цезаря

Base64 — это стандартное представление двоичных данных через символы из набора из 64 знаков. Каждая четвёрка символов однозначно восстанавливает исходные байты.

В решении для каждой группы из 4 символов:

• каждый символ переводится в число от 0 до 63;
• из этих чисел собираются исходные 24 бита;
• из них извлекаются исходные байты.

Если в конце стоят символы '=', решение корректно не добавляет лишние байты. Значит, после завершения этого этапа получается в точности та строка, которая была до кодирования Base64, то есть строка после применения шифра Цезаря.

Шаг 2. Обратный сдвиг Цезаря восстанавливает исходный текст

Шифр Цезаря со сдвигом k вперёд переводит каждую букву в букву, отстоящую на k позиций дальше по кругу.

Чтобы отменить этот сдвиг, нужно сдвинуть букву назад на k позиций. Именно это делает формула:

'A' + (ch - 'A' - k + 26) % 26

Она работает циклически:

• если буква не выходит за левую границу алфавита, просто сдвигается назад;
• если выходит, то переходит к концу алфавита.

Пробелы не являются буквами, поэтому они остаются без изменений.

Вывод

После Base64-декодирования мы получаем строку после Цезаря, а после обратного сдвига Цезаря — исходный открытый текст. Значит, алгоритм корректен.

5. Сложность

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

• Декодирование Base64 обрабатывает строку по 4 символа, то есть работает за O(n).
• Обратный сдвиг по декодированной строке тоже работает за O(n).

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

Дополнительная память:

• хранение декодированной строки и ответа — O(n).

6. Код на C++17

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

using namespace std;

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

    vector<int> val(256, -1);
    for (int i = 0; i < 26; i++) val['A' + i] = i;
    for (int i = 0; i < 26; 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) {
        int a = val[(unsigned char)s[i]];
        int b = val[(unsigned char)s[i + 1]];
        int c = (s[i + 2] == '=') ? 0 : val[(unsigned char)s[i + 2]];
        int d = (s[i + 3] == '=') ? 0 : val[(unsigned char)s[i + 3]];

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

        decoded.push_back(char((triple >> 16) & 255));
        if (s[i + 2] != '=') {
            decoded.push_back(char((triple >> 8) & 255));
        }
        if (s[i + 3] != '=') {
            decoded.push_back(char(triple & 255));
        }
    }

    string ans = decoded;
    for (int i = 0; i < (int)ans.size(); i++) {
        if ('A' <= ans[i] && ans[i] <= 'Z') {
            ans[i] = char('A' + (ans[i] - 'A' - k + 26) % 26);
        }
    }

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

7. Код на Python 3

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

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

decoded_chars = []

for i in range(0, len(s), 4):
    a = val[s[i]]
    b = val[s[i + 1]]
    c = 0 if s[i + 2] == '=' else val[s[i + 2]]
    d = 0 if s[i + 3] == '=' else val[s[i + 3]]

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

    decoded_chars.append(chr((triple >> 16) & 255))
    if s[i + 2] != '=':
        decoded_chars.append(chr((triple >> 8) & 255))
    if s[i + 3] != '=':
        decoded_chars.append(chr(triple & 255))

decoded = ''.join(decoded_chars)

ans = []
for ch in decoded:
    if 'A' <= ch <= 'Z':
        ans.append(chr(ord('A') + (ord(ch) - ord('A') - k) % 26))
    else:
        ans.append(ch)

print(''.join(ans))