1. Идея

Нужно поддерживать текущее положение в файловой системе и обрабатывать две команды:

• cd path — перейти по пути;
• pwd — вывести текущий абсолютный путь.

Самая удобная модель текущего каталога — хранить его как список компонент пути.

Например:

• / хранится как пустой список [];
• /a/b/c хранится как ["a", "b", "c"].

Тогда:

• перейти в подкаталог x — это добавить x в конец списка;
• перейти на уровень вверх .. — это удалить последний элемент, если он есть;
• команда pwd — это просто вывести / и соединить все компоненты через /.

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

1. Абсолютный и относительный путь обрабатываются почти одинаково

Разница только в точке старта:

• если путь начинается с /, то сначала надо перейти в корень, то есть очистить текущий список компонент;
• иначе начинаем от текущего каталога.

После этого можно одинаково разбирать путь по частям.

2. Путь надо разбить на компоненты по символу /

По условию несколько / подряд считаются одним разделителем, а пустые компоненты игнорируются.

Значит, если после разбиения получается пустая строка, её просто пропускаем.

Например, путь a//b///c эквивалентен a/b/c.

3. Компоненты . и .. обрабатываются отдельно

Для каждой компоненты:

• . — ничего не меняет;
• .. — поднимает на один уровень вверх, но из корня выше подняться нельзя;
• любое другое имя — обычный переход в подкаталог, добавляем его в список.

4. Корень удобно хранить как пустой список

Это сильно упрощает код:

• если список пуст, то текущий путь — /;
• если встретили .. и список пуст, просто ничего не делаем.

3. Алгоритм

Будем хранить текущий путь в массиве cur.

Для каждой команды:

Команда pwd

• Если cur пуст:
  • выводим /.
• Иначе:
  • выводим строку вида "/" + компоненты через "/".

Команда cd path

1. Извлекаем строку path.
2. Если path начинается с /, очищаем cur, потому что путь абсолютный.
3. Разбиваем path на компоненты по символу /.
4. Для каждой компоненты:
   • если она пустая, пропускаем;
   • если это ., пропускаем;
   • если это .., удаляем последнюю компоненту из cur, если она есть;
   • иначе добавляем компоненту в cur.

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

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

Будем считать, что список cur в любой момент равен компонентам абсолютного пути текущего каталога.

После команды pwd

Команда ничего не меняет, только выводит путь.

• Если cur пуст, это корень, и по условию нужно вывести /.
• Иначе путь состоит из всех компонент cur, записанных через / с ведущим /.

Значит, вывод корректен.

После команды cd path

Рассмотрим два случая.

Случай 1. Путь абсолютный

Если path начинается с /, переход должен выполняться от корня.

Алгоритм очищает cur, то есть переводит текущее состояние в корень. Это ровно соответствует условию.

Случай 2. Путь относительный

Если path не начинается с /, переход должен выполняться от текущего каталога.

Алгоритм не очищает cur, то есть стартует из текущего пути. Это тоже соответствует условию.

Дальше обрабатываются компоненты пути по порядку.

Обработка одной компоненты

• Пустая компонента возникает из-за нескольких / подряд. По условию такие компоненты игнорируются. Алгоритм именно это и делает.
• . означает текущий каталог, то есть ничего менять не нужно. Алгоритм ничего не меняет.
• .. означает переход на один уровень вверх. Если текущий каталог не корень, надо убрать последнюю компоненту. Если уже корень, остаться в корне. Алгоритм делает ровно это.
• Обычное имя означает переход в подкаталог с этим именем. Алгоритм добавляет компоненту в конец списка, что и соответствует такому переходу.

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

Следовательно, после каждой команды cd список cur снова равен текущему абсолютному пути.

5. Сложность

Пусть суммарная длина всех путей во входных данных равна S.

Тогда:

• разбор каждой команды cd работает за время, линейное от длины её пути;
• команда pwd выводит текущий путь, и её стоимость пропорциональна длине выводимой строки.

С учётом ограничения на суммарную длину входных путей и вывода общая сложность составляет:

• по времени: O(S)
• по памяти: O(S) в худшем случае для хранения текущего пути

На практике память для cur равна длине текущего пути.

6. Код на C++17

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

using namespace std;

int main() {
    int q;
    cin >> q;
    string line;
    getline(cin, line);

    vector<string> cur;

    for (int i = 0; i < q; i++) {
        getline(cin, line);

        if (line == "pwd") {
            if (cur.empty()) {
                cout << "/" << '\n';
            } else {
                cout << "/";
                for (int j = 0; j < (int)cur.size(); j++) {
                    if (j > 0) cout << "/";
                    cout << cur[j];
                }
                cout << '\n';
            }
            continue;
        }

        string path = line.substr(3);
        if (!path.empty() && path[0] == '/') {
            cur.clear();
        }

        string part = "";
        for (int j = 0; j <= (int)path.size(); j++) {
            if (j == (int)path.size() || path[j] == '/') {
                if (!part.empty()) {
                    if (part == ".") {
                    } else if (part == "..") {
                        if (!cur.empty()) cur.pop_back();
                    } else {
                        cur.push_back(part);
                    }
                }
                part.clear();
            } else {
                part += path[j];
            }
        }
    }

    return 0;
}

7. Код на Python 3

q = int(input())
cur = []

for _ in range(q):
    line = input()

    if line == "pwd":
        if not cur:
            print("/")
        else:
            print("/" + "/".join(cur))
        continue

    path = line[3:]
    if path and path[0] == "/":
        cur = []

    parts = path.split("/")
    for part in parts:
        if part == "":
            continue
        if part == ".":
            continue
        if part == "..":
            if cur:
                cur.pop()
        else:
            cur.append(part)