CS
Задачник Базовый курс EN

Задача

Права доступа

битовые трюки симуляция операционные системы

У каждого файла в Unix девять прав: чтение (r), запись (w) и исполнение (x) для владельца (u), группы (g) и всех остальных (o). Их пишут восьмеричным числом из трёх цифр — например, 754 — или строкой rwxr-xr--: каждая цифра — три бита одного класса, старший бит — чтение, младший — исполнение.

Команда chmod меняет права двумя способами. Восьмеричное число задаёт все права сразу. Символьная запись — это одно или несколько условий через запятую. Условие — классы (u, g, o в любом сочетании или a — все три), потом знак и права (r, w, x, возможно ни одного):

  • + — добавить эти права выбранным классам;
  • - — убрать;
  • = — у выбранных классов оставить ровно эти права, остальные убрать.

Условия применяются слева направо. Начав с заданных прав, выполните команды по очереди и после каждой выведите права.

Вход

В первой строке начальные права — три восьмеричные цифры. Во второй — число команд q (1 ≤ q ≤ 2·10⁵). Дальше q строк по команде, без пробелов.

Выход

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

Примеры

Пример 1

Вход
644
10
u+x
go-r
g+rx
o=r
a+w
a-x
u=rwx,g=rx,o=
750
g=
o+rwx
Выход
744 rwxr--r--
700 rwx------
750 rwxr-x---
754 rwxr-xr--
776 rwxrwxrw-
666 rw-rw-rw-
750 rwxr-x---
750 rwxr-x---
700 rwx------
707 rwx---rwx

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
5 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Права — это девять бит одного числа. Какой маской выбрать класс «группа»? А право «запись» во всех классах сразу?

2Идея

Маска класса: u — 0o700, g — 0o070, o — 0o007, a — 0o777; несколько классов складываются через «или». Маска права во всех классах: r — 0o444, w — 0o222, x — 0o111. Пересечение двух масок — ровно те биты, которые трогает условие. Дальше одна битовая операция: + — «или», - — «и» с отрицанием, = — сначала стереть весь класс, потом поставить биты.

3Разбор

В примере: 644 — это rw-r--r--. u+x добавляет бит 0o100 и даёт 744; go-r стирает 0o044 и даёт 700; o=r на 750 сначала стирает класс остальных (0o007 — там и так пусто), потом ставит 0o004 — 754. Восьмеричная запись удобна именно тем, что каждая цифра — ровно один класс: 7 = 4 + 2 + 1 = rwx, 5 = 4 + 1 = r-x.

Знак = — главная ловушка. Если обработать его как +, старые права класса останутся: o=r на rwxrwxrwx должно дать rwxrwxr--, а не оставить всё как было. Подробнее о масках, флагах и наборах-как-числах — в статье «Битовые трюки».

3+Решение
4Сложность

O(длины команды) на команду: по символу — одна битовая операция.

5Типичные ошибки
  • = как +. Не стирает старые права класса — уже первый тест.
  • Забыть про несколько классов. go-r убирает чтение у группы и у остальных сразу: маски классов складываются.
  • Пустой набор прав. g= — законная команда: у группы не остаётся ничего.
  • Ведущие нули. Права 007 печатаются как 007, а не 7.

Алгоритмы задачи

TEC Приём Битовые трюки Число как набор флажков: маски, младшая единица, подсчёт единиц и перебор подмножеств без рекурсии. O(1) на операцию над словом 1 задача
Каталог алгоритмов