67 lines
4.9 KiB
Markdown
67 lines
4.9 KiB
Markdown
# Grupuri / Группы
|
||
* Городская олимпиада Кишинева по информатике
|
||
* Год 2022
|
||
* 12 класс
|
||
* Задача 3
|
||
|
||
Фирма ABC-Soft имеет `m` служащих и располагает компьютерной сетью. Каждый пользователь идентифицируется с помощью индивидуального целого числа, состоящего из шести цифр. Сервер сети предоставляет в общее пользование жесткий диск, корневой каталог которого имеет `n` подкаталогов. Для каждого подкаталога существует список, в котором указаны пользователи, имеющие доступ к его файлам. В общем случае
|
||
пользователь имеет доступ к одному или к нескольким подкаталогам.
|
||
|
||
|
||
Администратор сети желает разбить множество пользователей на отдельные группы. Два пользователя могут быть включены в одну и ту же группув том и только в том случае если оба имеют доступ к одним и тем же подкаталогам.
|
||
|
||
|
||
Напишите программу, которая получая на входе списки пользователей каждого из подкаталогов, вычисляет количество групп пользователей `К`.
|
||
|
||
# Входные данные
|
||
Текстовый файл `grupuri.in` содержит в первой строке одно целое число - количество тестов `T`. Далее следуют `T` тестов. В первой строке теста находится количество подкаталогов `n`. Следующие `n` строк входного файла содержат списки пользователей, по одному списку в каждой строке. Первым в строке `i + 1` записано целое число `m[i]` количество пользователей которые имеют доступ к файлам из подкаталога `і`, далее, в том же строке записаны идентификационные номера соответствующих пользователей, все числа разделены пробелами.
|
||
|
||
|
||
# Выходные данные
|
||
Текстовый файл `grupuri.out` должен содержать в единственной строке целое число — число групп пользователей `k`.
|
||
|
||
# Ограничения
|
||
* 1 <= n <= 100.
|
||
* Для первых 10 тестов 1 <= m <= 100; 1 <= m[i] <= 100, i = 1, 2, 3, ..., п.
|
||
* Для следующих 10 тестов 1 <= m <= 10000; 1 <= m[i] <= 10000, i = 1, 2, 3, ..., п.
|
||
* Идентификационные номера пользователей состоят из шести цифр, включая, при необходимости, незначащие нули, и находятся в интервале [1, 999999].
|
||
* Ограничения на время выполнения и на объем используемой памяти приведены на странице «Общее описание задач».
|
||
* Исходный файл должен иметь имя grupuri.pas, grupuri.c или grupuri.cpp.
|
||
|
||
|
||
# Пример
|
||
`tests.in`
|
||
|
||
```
|
||
1
|
||
5
|
||
2 010000 020000
|
||
3 020000 010000 999999
|
||
3 020000 999999 010000
|
||
1 999999
|
||
2 O30000 999999
|
||
```
|
||
|
||
`tests.out`
|
||
```
|
||
3
|
||
```
|
||
|
||
# Объяснение
|
||
Все участники группы должны иметь допступ ко всем подкаталогам,
|
||
к которым имеет доспут каждый член группы.
|
||
```
|
||
группа) подкаталоги (служащие)
|
||
|
||
a) 1, 2, 3 (1, 2)
|
||
b) 2, 3, 4, 5 (9)
|
||
c) 5 (3)
|
||
```
|
||
|
||
Группа a) имеет доступ к 1, 2, 3 подкаталогам (все её участники должны иметь доспут к этим подкаталогам).
|
||
|
||
|
||
Группа b) имеет доступ к 2, 3, 4, 5 подкаталогам. К этим подкаталогам имеет доступ только 1 служащий `9`.
|
||
|
||
Группа c) имеет доступ к 5 подкаталогу. В неё входит служащий `3`. В неё не может входить служащий `9`, потому что в таком случае все участники этой группы должны иметь доспут к подкаталогам `9` служащего, а служащий `3` имеет доступ только к 5-му подкаталогу.
|