1. Идея

Дан текст, зашифрованный шифром Цезаря со сдвигом k. Это значит, что при шифровании каждая заглавная латинская буква была сдвинута вперёд на k позиций по кругу.

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

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

1. Заглавные латинские буквы идут подряд: от A до Z.
2. Удобно заменить букву её номером в алфавите:
   • A -> 0
   • B -> 1
   • ...
   • Z -> 25
3. Если буква имела номер x, то после расшифровки она должна перейти в: x - k
4. Так как алфавит циклический, нужно брать остаток по модулю 26: (x - k + 26) % 26
5. После этого можно снова превратить номер в букву.
6. По условию текст состоит из заглавных латинских букв и пробелов, но решение корректно оставляет без изменений вообще все символы, которые не лежат в диапазоне от A до Z.

3. Алгоритм

1. Считать число k.
2. Считать всю вторую строку целиком.
3. Завести пустую строку ответа.
4. Для каждого символа c в тексте:
   • если c — заглавная латинская буква:
     • найти её номер x = c - 'A';
     • вычислить новый номер x = (x - k + 26) % 26;
     • добавить в ответ букву 'A' + x;
   • иначе добавить символ в ответ без изменений.
5. Вывести получившийся текст.

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

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

При шифровании её номер в алфавите p превращается в: (p + k) % 26

Пусть в шифротексте получилась буква с номером x. Тогда: x = (p + k) % 26

Чтобы восстановить исходную букву, нужно вычесть k: (x - k + 26) % 26

Подставим значение x: ((p + k) % 26 - k + 26) % 26

Это выражение равно p, то есть мы получаем исходную букву.

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

Значит, каждый символ обрабатывается правильно, и весь текст расшифровывается верно.

5. Сложность

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

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

6. Код на C++17

#include <iostream>
#include <string>
using namespace std;

int main() {
    int k;
    cin >> k;
    cin.ignore();

    string s;
    getline(cin, s);

    string ans;
    for (char c : s) {
        if (c >= 'A' && c <= 'Z') {
            int x = c - 'A';
            x = (x - k + 26) % 26;
            ans += char('A' + x);
        } else {
            ans += c;
        }
    }

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

7. Код на Python 3

k = int(input())
s = input()

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

print(''.join(ans))