| Автор: | А. Баранов | Ограничение времени: | 1 сек | |
| Входной файл: | test.db | Ограничение памяти: | 256 Мб | |
| Выходной файл: | test.log |
Для поддержания структуры файловой системы с иерархической организацией каталогов используется база данных специального вида.
Информация об имеющихся в наличии файлах и каталогах содержится в таблице ITEMS:
| ROWI INTEGER PRIMARY KEY, NAME CHAR(255) NOT NULL, TYPE BOOLEAN NOT NULL, ... ; |
Здесь поле TYPE может принимать одно из следующих значений: 0 — регулярный файл; 1 — каталог.
В свою очередь, информация о связях между элементами хранится в таблице LINKS:
| ROWI INTEGER PRIMARY KEY, | |
| ROOT INTEGER REFERENCES ITEMS(ROWI), | — ссылка на родительский каталог; |
| ITEM INTEGER REFERENCES ITEMS(ROWI); | — ссылка на внутренний элемент. |
Для доступа к файлам и подкаталогам используются символьные пути, включающие имена всех промежуточных каталогов.
Процедура слияния двух каталогов заключается в добавлении тех элементов,
которые отсутствуют в одном, но имеются в другом каталоге.
В процессе слияния возможны коллизии, связанные с наличием в обоих каталогах файлов (либо файла с подкаталогом),
доступных по одним и тем же символьным путям.
При этом существование двух таких подкаталогов коллизией не считается.
Каталоги, не привязанные к какому либо родителю, считаются корневыми.
Необходимо сравнить все имеющиеся пары корневых каталогов,
оценив число коллизий между ними.
В качестве ответа нужно вывести таблицу из трех столбцов:
ROWI первого каталога,
ROWI второго каталога,
число коллизий.
Результат выборки должен быть отсортирован в порядке возрастания по первым двум столбцам.
При этом значения в 1-м столбце должны быть строго меньше, чем во втором.
Записи с нулевым числом коллизий в выборку не добавляются!
Решение следует представить в виде текстового файла, содержащего единственный SQL-запрос.
Полагается, что для работы с базой данных используется SQLite3.
Имена файлов и каталогов состоят из цифр и букв латинского алфавита,
при этом заглавные и строчные символы неразличимы между собой.
Гарантируется, что в БД отсутствуют циклические зависимости,
а каждый элемент имеет не более одного предка.