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

Объяснение

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

группа) подкаталоги (служащие)

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-му подкаталогу.

4.9 KiB Raw Permalink Blame History Unescape Escape