1. Идея

Нужно пройти по строке слева направо и построить ответ.

Для каждого символа возможны три случая:

• если это +, то в ответ нужно добавить пробел;
• если это %, то следующие два символа образуют шестнадцатеричное число XX, которое задаёт ASCII-код символа; этот символ нужно добавить в ответ;
• иначе символ просто переносится в ответ без изменений.

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

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

1. Последовательность %XX всегда корректна по условию. Это значит, что если встретился символ %, то после него точно идут две шестнадцатеричные цифры.

2. После обработки %XX нужно перейти сразу через три позиции:

   • %
   • первая цифра
   • вторая цифра

3. Символ + всегда превращается именно в пробел ' '.

4. Остальные символы не требуют никакой дополнительной обработки.

5. В C++ удобно написать небольшую функцию, которая переводит один шестнадцатеричный символ в число:

   • '0'...'9' -> 0...9
   • 'A'...'F' -> 10...15
   • 'a'...'f' -> 10...15

3. Алгоритм

Пусть дана строка s.

1. Создаём пустую строку ответа.
2. Идём по строке слева направо.
3. Если текущий символ равен +, добавляем в ответ пробел.
4. Если текущий символ равен %, то:
   • берём два следующих символа;
   • переводим их из шестнадцатеричной записи в число;
   • добавляем в ответ символ с таким ASCII-кодом;
   • пропускаем ещё две позиции.
5. Иначе добавляем текущий символ в ответ как есть.
6. Выводим полученную строку.

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

Докажем, что алгоритм строит именно правильную декодированную строку.

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

Случай 1: текущий символ — +

По условию задачи каждый символ + нужно заменить пробелом. Алгоритм делает ровно это, значит обработка верна.

Случай 2: текущий символ — %

По условию каждая подстрока вида %XX означает символ с ASCII-кодом, записанным шестнадцатерично. Алгоритм берёт ровно эти два символа XX, переводит их в число и добавляет соответствующий символ в ответ. Затем он пропускает уже использованные два символа. Значит, такая подстрока декодируется правильно.

Случай 3: любой другой символ

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

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

5. Сложность

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

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

6. Код на C++17

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

using namespace std;

int hexValue(char c) {
    if ('0' <= c && c <= '9') return c - '0';
    if ('A' <= c && c <= 'F') return c - 'A' + 10;
    return c - 'a' + 10;
}

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

    string result;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '+') {
            result += ' ';
        } else if (s[i] == '%') {
            int value = hexValue(s[i + 1]) * 16 + hexValue(s[i + 2]);
            result += char(value);
            i += 2;
        } else {
            result += s[i];
        }
    }

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

7. Код на Python 3

s = input()

res = []
i = 0

while i < len(s):
    if s[i] == '+':
        res.append(' ')
        i += 1
    elif s[i] == '%':
        value = int(s[i + 1:i + 3], 16)
        res.append(chr(value))
        i += 3
    else:
        res.append(s[i])
        i += 1

print(''.join(res))