Алгоритмы

 

Примеры

№	Входные данные	Выходные данные
1	1	1
2	7	21

Вы разрабатываете систему, одной из задач которой является составление расписания работы над задачами, выполняемыми некоторой организацией, занимающейся разработкой программного обеспечения.

Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число a_i — номер дня, ранее которого не может быть начато выполнение этой задачи.

Ваша программа должна, имея информацию о количестве задач и днях, ранее которых выполнение задач не может быть начато, определить количество допустимых расписаний выполнения задач—  количество таких расписаний, при которых каждая задача выполняется не ранее указанного для нее дня.

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

В первой строке находится натуральное число n (1 ≤ n ≤ 8) — количество задач, которые необходимо выполнить.

Следующая строка содержит n натуральных чисел a_i (1 ≤ a_i ≤ n) — для каждой работы номер дня, ранее которого не может быть начато выполнение этой задачи. Числа отделены друг от друга одним пробелом.

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

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

Пример входных и выходных данных

Ввод	Вывод
5 2 4 4 2 1	4

Вы разрабатываете систему управления персоналом в некоторой фирме. В фирме работают n сотрудников. Каждый сотрудник характеризуется своим порядковым номером, который является натуральным числом от одного до n. Номера всех сотрудников различны.

Сотрудник, имеющий порядковый номер один, является главой фирмы. У каждого из всех остальных сотрудников имеется один непосредственный начальник — сотрудник фирмы, имеющий меньший порядковый номер.

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

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

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

В первой строке находится натуральное число n (2 ≤ n ≤ 100) — количество сотрудников в фирме.

Следующая строка содержит n-1 натуральное число — номера непосредственных начальников сотрудников с номерами от 2 до n в соответствующем порядке. Числа отделены друг от друга одним пробелом. Гарантируется, что номер непосредственного начальника очередного сотрудника меньше номера самого сотрудника.

Следующая строка содержит одно натуральное число x (1 ≤ x ≤ n) — номер отправляемого в командировку сотрудника.

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

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

Пример входных и выходных данных

Ввод	Вывод
9 1 2 1 4 4 2 7 8 2	4

Вы разрабатываете систему, одной из задач которой является составление расписания работы над задачами, выполняемыми некоторой организацией, занимающейся разработкой программного обеспечения.

Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число a_i — номер дня, не позднее которого эта задача должна быть выполнена.

Ваша программа должна, имея информацию о количестве задач и днях, не позднее которых должны быть выполнены задачи, определить количество допустимых расписаний выполнения задач—  количество таких расписаний, при которых каждая задача выполняется не позднее указанного для нее дня.

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

В первой строке находится натуральное число n (1 ≤ n ≤ 8) — количество задач, которые необходимо выполнить.

Следующая строка содержит n натуральных чисел a_i (1 ≤ a_i ≤ n) — для каждой работы номер дня, не позднее которого она должна быть выполнена. Числа отделены друг от друга одним пробелом.

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

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

Пример входных и выходных данных

Ввод	Вывод
5 2 4 4 2 5	4

Вы разрабатываете систему управления персоналом в некоторой фирме. В фирме работают n сотрудников. Каждый сотрудник характеризуется своим порядковым номером, который является натуральным числом от одного до n. Номера всех сотрудников различны.

Сотрудник, имеющий порядковый номер один, является главой фирмы. У каждого из всех остальных сотрудников имеется один непосредственный начальник — сотрудник фирмы, имеющий меньший порядковый номер.

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

Вам необходимо, зная структуру фирмы и номер отправляемого в командировку сотрудника, сообщить, сколько сотрудников отправятся в командировку в результате выполнения этой операции.

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

В первой строке находится натуральное число n (2 ≤ n ≤ 100) — количество сотрудников в фирме.

Следующая строка содержит n-1 натуральное число — номера непосредственных начальников сотрудников с номерами от 2 до n в соответствующем порядке. Числа отделены друг от друга одним пробелом. Гарантируется, что номер непосредственного начальника очередного сотрудника меньше номера самого сотрудника.

Следующая строка содержит одно натуральное число x (1 ≤ x ≤ n) — номер отправляемого в командировку сотрудника.

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

выведите одно число — количество сотрудников, отправляющихся в командировку после выполнения описанной операции.

Пример входных и выходных данных

Ввод	Вывод
9 1 2 1 4 4 2 7 8 2	5

 

Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.

Входные данные: В первой строке содержатся два натуральных числа n и m (1≤n≤10⁵, 1≤m≤10⁵) — количество вершин и рёбер в графе соответственно. Далее в m строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно (нумерация вершин начинается с 1).
Примеры

№	Входные данные	Выходные данные
1	4 4 1 4 4 3 4 2 3 2	1 4 3 2

 

Примеры

№	Входные данные	Выходные данные
1	3	2

Напишите программу, которая в последовательности натуральных чисел подсчитывает количество тех чисел, которые одновременно удовлетворяют двум условиям:

1. Оканчиваются на 0 в системе счисления с основанием 9;
2. Не оканчиваются на 0 в системе счисления с основанием 7.

Формат входных данных

В первой строке задаётся количество элементов \(N\) (\(1 \le N \le 1000\)). В каждой из следующих \(N\) строк — одно натуральное число.

Формат выходных данных

Одно целое число — количество подходящих чисел.

Пользователь вводит количество слов, а затем сами слова — каждое на отдельной строке. Сохраните все слова в список.

Выведите две строки:

1. Исходный список — слова через пробел в порядке ввода.
2. Отсортированный список — слова через пробел по возрастанию длины. Если длины равны, сохраните порядок ввода.

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 15\)).

Следующие \(N\) строк — по одному слову (строчные русские буквы, без пробелов).

Формат выходных данных

Две строки: исходный список и отсортированный по возрастанию длины, слова через пробел.

Примечание

Подсказка: используйте key=len в функции sorted().

Пользователь вводит количество чисел, а затем сами числа — каждое на отдельной строке. Сохраните все числа в список.

Выведите две строки:

1. Исходный список — числа через пробел в порядке ввода.
2. Отсортированный список — числа через пробел по возрастанию их модуля (абсолютного значения). Если модули равны, сохраните порядок ввода.

Формат входных данных

Первая строка — целое число \(N\) (\(1 \le N \le 20\)).

Следующие \(N\) строк — по одному целому числу (от \(-1000\) до \(1000\)).

Формат выходных данных

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

Примечание

Модуль числа — это число без знака. Например, модуль числа \(-7\) равен \(7\), модуль числа \(3\) равен \(3\).

Подсказка: используйте key=abs в функции sorted().

Пользователь вводит несколько целых чисел в одной строке через пробел. Выведите три строки: минимальное число, максимальное число и все числа в отсортированном порядке (по возрастанию).

Формат входных данных

Одна строка — целые числа через пробел (от 2 до 20 чисел, каждое от \(-1000\) до \(1000\)).

Формат выходных данных

Три строки:

1. Минимальное число.
2. Максимальное число.
3. Все числа в порядке возрастания через пробел.

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

Формат входных данных

Одна строка — имена через пробел (от 2 до 15 имён). Все имена начинаются с заглавной буквы, остальные строчные. Имена состоят только из русских букв.

Формат выходных данных

Одна строка — имена в алфавитном порядке через пробел.

Пользователь вводит несколько целых чисел в одной строке через пробел. Выведите их в порядке убывания.

Формат входных данных

Одна строка — целые числа через пробел (от 2 до 20 чисел, каждое от \(-1000\) до \(1000\)).

Формат выходных данных

Одна строка — те же числа, отсортированные по убыванию, через пробел.

Пользователь вводит несколько слов через пробел. Постройте словарь, где ключ — слово, значение — его длина. Выведите пары в формате слово: длина, отсортированные по длине в порядке возрастания. Если длины одинаковые, сортируйте по алфавиту.

Формат входных данных

Одна строка — слова через пробел (от 2 до 15 слов). Все слова различны.

Формат выходных данных

Строки в формате слово: длина, отсортированные по длине (по возрастанию), при равенстве — по алфавиту.

В ресторане отеля есть \(n\) видов специй. Каждый день повар выбирает \(m\) из них для главного блюда дня. Помощник главного повара тестирует блюдо и после этого оно поступает на обед в ресторан.

Известно, что у помощника есть аллергия на \(k\) видов специй, имеющихся в ресторане. Сегодня он протестировал блюдо и аллергии не возникло.

На обед пришло \(p\) человек, у каждого из которых тоже есть аллергия на некоторые виды специй. Попробуйте для каждого из участников обеда предположить, может ли у них возникнуть аллергия на главное блюдо?

В первой содержатся целые числа \(n\) и \(m\) (\(1 \le m \le n \le 100\)) — число специй на складе и количество специй в главном блюде соответственно.

Далее в отдельной строке идет число \(k\) (\(0 \le k \le n\)) — число специй, на которые аллергия у помощника повара.

В следующих \(k\) строках содержатся названия специй, на которые есть аллергия у помощника повара.

В следующей строке написано число \(p\) (\(1 \le p \le 100\)) — число людей на обеде. Далее идет \(p\) блоков, описывающих специи, опасные для \(i\)-го участника обеда. Каждый блок начинается строкой с числом \(n_i\) (\(0 \le n_i \le n\)) — количеством продуктов, на которые аллергия у \(i\)-го человека, вслед за которым идёт \(n_i\) строк с названиями аллергенных специй.

Все названия — слова из латинских букв длиной не более 30 символов.

Для каждого из \(p\) запросов выведите на отдельной строке одно слово:

• NO, если обед будет полностью безвреден для очередного гостя;

• YES, если в главном блюде есть специя аллергенная для гостя;

• MAYBE, если при таких исходных данных возможна и та, и другая ситуация.

Управляющий отелем давно мечтал приобрести новую мебель на свою дачу...

В Отель привезли \(N\) новых стульев. Их нужно расставить во все комнаты гостиницы. Вместимость каждой комнаты \(a_i\) гостей, то есть, изначально предполагалось, что в этой комнате будет ровно \(a_i\). Администратор хочет сэкономить на расстановке стульев в комнатах и забрать <<лишние>> стулья на дачу.

Но есть условия, которые необходимо соблюдать при расстановке:

• в каждой комнате должен быть хотя бы один стул;

• во всех комнатах может не хватать только одинакового количества стульев.

Какое максимально возможное количество стульев может сэкономить администратор в данных условиях?

Формат входных данных
В первой строке вводится два числа \(N\) (\(1\le N\le 10^9\)) — количество привезенных стульев и \(K\) (\(1\le K\le 100\,000\)) — количество комнат в Отеле.

Далее в одной строке через пробел записаны \(K\) натуральных чисел, не превосходящих \(1000\) — вместимости комнат.

Гарантируется, что исходного количества стульев хватает для расстановки по комнатам с учетом необходимых требований.

Формат выходных данных
Нужно вывести единственное число — количество стульев, которые останутся после максимально экономной расстановки стульев по комнатам.

В примере из условия если в первую комнату поставить 1, во вторую — 2, в третью — 3, в четвёртую — 4, а в пятую — 5 стульев, то в каждой из комнат будет не хватать ровно одного стула, а администратор сможет сэкономить ровно пять стульев.