Мини-урок · перед практикой

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

Сопоставляем файлам разрешения, а названиям операций — буквы.

О задаче

Как к ней подойти

Потренируйтесь хранить пары «ключ - значение» и находить нужные записи в словаре.

Коротко о теме

Словарь связывает ключ со значением и позволяет быстро найти запись по ключу. Решите, что будет ключом, что значением и как обрабатывать отсутствующую запись. Для подсчётов удобно начинать с нуля.

Ключевая идея · Множества разрешений

Запрос сводится к проверке одной буквы в разрешениях конкретного файла.

Проверьте перед запуском

В запросе сначала операция, затем файл; execute соответствует X, а не E.

После практики

Сравните свой подход

Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.

Ваше принятое решение

Рекомендуемое решение: Множества разрешений

Запрос сводится к проверке одной буквы в разрешениях конкретного файла.

rights = {}
for _ in range(int(input())):
    name, *allowed = input().split()
    rights[name] = set(allowed)
operation = {'read': 'R', 'write': 'W', 'execute': 'X'}
for _ in range(int(input())):
    action, name = input().split()
    print('OK' if operation[action] in rights[name] else 'Access denied')

Время: O(N+M) в среднем. Память: O(N) записей.

Другой способ: Битовые маски

Каждому праву выделяем один бит; побитовое И проверяет наличие нужного бита.

bits = {'R': 1, 'W': 2, 'X': 4}
rights = {}
for _ in range(int(input())):
    name, *allowed = input().split()
    mask = 0
    for letter in allowed:
        mask |= bits[letter]
    rights[name] = mask
operation = {'read': 1, 'write': 2, 'execute': 4}
for _ in range(int(input())):
    action, name = input().split()
    print('OK' if rights[name] & operation[action] else 'Access denied')

Время: O(N+M) в среднем. Память: O(N) записей.