410411: GYM104018 D Невиданная наглость!

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Невиданная наглость!ограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Вчера вечером случилось нечто неслыханное: уезжая со стоянки, кто-то из сотрудников поцарапал автомобиль Самого Главного Начальника!

Кто это был, пока неизвестно, но Самый Главный Начальник успел заметить, что кто-то из сотрудников был на перекуре ровно в момент проишествия.

Самый Главный Начальник в бешенстве! Он велит найти нарушителя, прямо здесь и сейчас. Вы, как начальник охраны, смогли немного успокоить Начальника и выбить немного времени.

Если точнее, то Самый Главный Начальник «в честь предстоящего $$$2023$$$ года» дал вам 23 дня на поиски.

Теперь ваша цель — найти того самого свидетеля-«перекурщика» и узнать у него личность нарушителя. Для этого вы планируете каждый день вызывать часть сотрудников компании на допрос.

Правда, есть два важных ограничения:

  1. Свидетель не сознается, если вместе с ним в один и тот же день вызовут нарушителя (не хочет портить отношения с коллегой);
  2. За один день вы можете допросить не более 70% работников компании (иначе производственные процессы совсем встанут).

Чтобы приступить к поискам, вам необходимо заранее подать в отдел кадров расписания всех допросов на все дни.

Для удобства всем сотрудникам присвоены уникальные номера от $$$1$$$ до $$$N$$$.

Помните, что из-за ограничения 1 вам необходимо запланировать все допросы таким образом, чтобы для каждой пары сотрудников ($$$i \ne j$$$) существовал хотя бы один допрос, что сотрудник $$$i$$$ присутствовал на допросе, а сотрудник $$$j$$$ — нет.

Входные данные

В единственной строке записано одно целое число $$$N$$$ ($$$2 \le N \le 2500$$$) — количество сотрудников, среди которых есть свидетель и нарушитель.

Выходные данные

В первой строке выведите целое число $$$D$$$ ($$$1 \le D \le 23$$$) — количество дней, в течение которых вы будете проводить допросы.

Каждая из следующих $$$D$$$ строк описывает один допрос в формате $$$k$$$ $$$w_1$$$ $$$w_2$$$ $$$\dots$$$ $$$w_k$$$ ($$$1 \le k \le 0.7 \times N$$$; $$$1 \le w_i \le N$$$; $$$w_i \ne w_j$$$) — количество приглашенных на допрос сотрудников и уникальные номера этих сотрудников.

Ответ будет считаться корректным, если для каждой пары сотрудников ($$$i \ne j$$$) существует хотя бы один допрос, что сотрудник $$$i$$$ присутствует на этом допросе, а сотрудник $$$j$$$ — нет.

Если существует несколько корректных вариантов распределения сотрудников по допросам, то выведите любой.

ПримерыВходные данные
4
Выходные данные
4
1 1
1 2
1 3
1 4
Входные данные
3
Выходные данные
3
2 2 3
2 1 3
2 1 2
Входные данные
6
Выходные данные
9
3 1 2 3
3 4 5 6
2 1 2
2 3 1
2 3 2
2 4 5
2 6 4
2 5 6
2 1 3
Примечание

Первый тестовый пример

Так как сотрудников для допроса всего $$$4$$$, то можно каждый день опрашивать ровно одного из них.

Это удовлетворяет обоим условиям:

  • Так как каждый день опрашивается только один сотрудник, то свидетель и нарушитель никогда не окажутся на одном допросе.
  • Каждый день вы вызываете только $$$1$$$ человека, что не превышает $$$0.7 \times 4 = 2.8$$$.

Второй тестовый пример

Во втором тестовом примере каждый день опрашивается по два сотрудника.

  • Для каждой пары ($$$i \ne j$$$) существует день, когда $$$i$$$ присутствует, а $$$j$$$ — нет.

    Например, если свидетель — $$$1$$$, а нарушитель — $$$3$$$, то во второй день свидетель не расскажет ничего, а в третий день — сообщит вам необходимую информацию.

  • Каждый день вы вызываете $$$2$$$ сотрудника, что не превышает $$$0.7 \times 3 = 2.1$$$.

加入题单

上一题 下一题 算法标签: