Темы --> Информатика --> Алгоритмы --> Перебор --> Комбинаторные структуры --> Разные комбинаторные структуры
---> 17 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 >> Отображать по:
#1679
Министры его величества
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Его Величество Король Бубей Второй пожелал назначить новый кабинет министров (информация о том, что случилось со старым – строго засекречена). К составу кабинета министров есть следующие пожелания:

1) министров должно быть как можно меньше (так ими легче управлять, да и на зарплате можно сэкономить);

2) для каждой области (строительство, финансы и т.д.) должен быть хотя бы один министр, который в ней разбирается.

На рассмотрение Его Величества поступило \(N\) кандидатур. Определите, сколько и каких людей должны получить министерские посты, с учетом пожеланий.

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

сначала вводится число \(N\) (натуральное, не превышает 10) – количество кандидатов в списке, затем вводится число \(K\) (натуральное, не превышает 20 – общее количество областей, в которых министры должны разбираться). Затем идет \(N\) строк следующего формата: в начале строки вводится число \(P_i\) (натуральное, не превышает \(K\)) – количество областей, в которых разбирается \(i\)-й кандидат, потом вводятся номера этих областей (натуральные числа, не превышают \(K\)).

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

сначала выведите количество министров, которое планируется назначить, исходя из требований задачи, затем перечислите номера подходящих кандидатов, в порядке возрастания. Если решений несколько, то выберите из них то, в котором участвуют кандидаты, идущие раньше по списку. Гарантируется, что решение существует (то есть можно получить такой набор кандидатов, что в каждой области будет разбираться хотя бы один из них)

Примеры
Входные данные
3 2
2 1 2
2 1 2
2 1 2
Выходные данные
1
1
Входные данные
4 3
1 1
1 2 
1 3
2 1 2
Выходные данные
2
3 4
#2762
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Разложение на простые множители числа \(12\) можно записать тремя способами:

\(\)12=2\cdot2\cdot3=2\cdot3\cdot2=3\cdot2\cdot2.\(\)

А сколькими способами можно записать разложение на простые множители числа \(N\)?

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

Вводится одно натуральное число \(N\) (\(2\le N\le 1 000\)).

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

Выведите одно число – количество различных записей разложения.

Примеры
Входные данные
12
Выходные данные
3
Входные данные
13
Выходные данные
1
#3486
5E: удалите скобки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дана скобочная последовательность из круглых скобок. Определить, какое минимальное количество скобок нужно удалить, чтобы получить ПСП.

Дана строка, составленная из круглых скобок. Определите, какое наименьшее количество символов необходимо удалить из этой строки, чтобы оставшиеся символы образовывали правильную скобочную последовательность.

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

Во входном файле записана строка из круглых скобок. Длина строки не превосходит \({100\,000}\) символов.

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

Выведите единственное целое число — ответ на поставленную задачу.

Примеры
Входные данные
())(()
Выходные данные
2
Входные данные
))(((
Выходные данные
5
#3487
5C: количество ПСП
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Посчитать количество таких ПСП из двух видов скобок, что внутри пары круглых скобок нет ни одной квадратной.

Посчитайте количество правильных скобочных последовательностей длины \(2n\) (\(n\) открывающихся скобок и \(n\) закрывающихся), составленных из круглых и квадратных скобок так, что внутри любой пары круглых скобок нет квадратных скобок.

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

В единственной строке через пробел записано целое неотрицательное число \(n\), не превосходящее 1000.

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

Выведите остаток от деления количества искомых правильных скобочных последовательностей на \(10^9+7\).

Примеры
Входные данные
1
Выходные данные
2
Входные данные
2
Выходные данные
7
#3488
5D: лексикографический порядок
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Сгенерировать все ПСП длины N.

Выведите все правильные скобочные последовательности заданной длины в лексикографическом порядке.

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

Во входном файле записана натуральное число \(n\), не превосходящее 10.

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

Выведите все правильные скобочные последовательности длины \(2n\) в лексикографическом порядке, по одной последовательности в строке.

Примеры
Входные данные
3
Выходные данные
((()))
(()())
(())()
()(())
()()()
Страница: << 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест