Информатика

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

Известно, что организации необходимо выполнить 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 остановок: маршрут начинается в первой из них, а заканчивается в n-й, соответственно. Всего в поезде имеется m мест для пассажиров.

Эта система будет использоваться для продажи билетов пассажирам. При покупке билета пассажир указывает номер станции L, на которой он хочет сесть на поезд и номер станции R, на которой он хочет сойти с поезда. Если у одного пассажира есть билет до станции S, а другой хочет купить билет от станции S, то они друг другу не мешают: второй может занимать только что освободившееся место первого. Система должна сообщить пассажиру следующую информацию:

• «YES», если в поезде есть свободные места. В этом случае пассажир покупает один билет с L-й по R-ю станцию.
• «NO», если подходящих свободных мест нет. В этом случае пассажир билет не покупает.

 

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

В первой строке находятся натуральные числа n (2 ≤ n ≤ 100), m (1 ≤ m ≤ 100) и k (1 ≤ k ≤ 100) — число станций в маршруте поезда, максимальное число пассажиров в поезде и число обращений обращений пассажиров к системе покупки билетов.

Следующие k строк содержат по два натуральных числа L_i и R_i (1 ≤ L_i < R_i ≤ n)  — начальная и конечная станции в i-м обращении к системе.

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

Для каждого обращения к системе в своей строке выведите её ответ: YES или NO.

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

Ввод	Вывод
5 2 4 1 4 1 3 2 5 3 5	YES YES NO YES

 

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

Входные данные: В первой строке содержатся два натуральных числа 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

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

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

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

В первой строке  находится одно натуральное число n (1 ≤ n ≤ 50) — количество гирек.
В каждой из следующих n строк находятся два натуральных числа a_i, b_i (1 ≤ a_i ≤ 1000, 1 ≤ b_i ≤ 2) — масса гири и номер чаши весов, на которой она находится.

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

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

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

Ввод	Вывод
5 4 2 1 1 8 1 5 2 2 1	20
6 20 2 3 2 2 1 5 1 1 1 3 2	32
4 3 2 10 2 8 2 9 2	30

На складе хранятся ящики разных цветов и размеров. Каждый цвет и каждый размер имеют свой порядковый номер в информационной системе.

Перед отправкой ящики упаковывают и сортируют. Упаковка и сортировка ящиков неэффективна и происходит следующим образом:

• Ящик под номером i поступает на склад.
• Ищется стопка, в которой хранятся ящики с размером, равным размеру i-го. Если такой стопки нет, формируется новая стопка.
• Поступающий ящик помещается наверх найденной или сформированной стопки.
• Если в какой-либо стопке оказывается два верхних ящика одного цвета, то они запаковываются и отправляются адресату.

Отправка продолжается до тех пор, пока не будут обработаны все поступающие на склад ящики.

 

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

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

В первой находятся три натуральных числа n, m, k (1 ≤ n, m, k ≤ 100) — количество ящиков, поступающих на склад, количество различных размеров и количество различных цветов соответственно.
В каждой из следующих n строк находятся по два натуральных числа x_i и y_i (1 ≤ x_i ≤ m; 1 ≤ y_i ≤ k)  — номер размера и номер цвета ящика, который поступит i-м на склад.

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

Требуется вывести одно число — сколько ящиков будут отправлены.

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

 

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

Даны даты N событий, произошедших после 1930 года: Название, год, номер месяца и число. Составить программу, организующую ввод информации в структуру и сравнивающую два любых события по времени. Необходимо вывести название события, которое произошло позже.

Входные данные
В первой строке вводится число N - количество событий (\(1<=N<=100\)). Далее идут N записей в формате (через пробел):
<Событие> <день события> <месяц> <год>.
Далее идет строка с указанием названий двух событий, которые необходимо сравнить:
<событие1> <событие2>.

Событие - одно слово, день события - число от 1 до 31, месяц  - число от 1 до 12,  год - число от 1937 до 2016.

Выходные данные
Выведите название события, которое произошло позже и его дату в формате:
<событие> <день события> <Месяц> <Год>.
Если два события произошли в один день, то выведите их названия через пробел (без указания даты):
<событие1> <событие2>. 
 

Примечание

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

Известна информация об N (0<N<=20) учениках класса: фамилия, имя, отчество  и дата рождения (день, месяц, год)
Определить структуру, описывающую информацию об учениках класса.
Вывести количество учеников в классе, у которых сегодня день рождения и их количество

Входные данные: 
В первой строке вводится число N - количество записей
Далее идут N записей в формате (через пробел): <Фамилия-слово без пробела> <Имя-слово без пробела> <Отчество-слово без пробела> <день рождения - число от 1 до 31> <Месяц рождения - число от 1 до 12> <Год рождения-число>
Далее идет строка с сегодняшней датой в формате  <день - число от 1 до 31> <Месяц - число от 1 до 12> <Год -число>

Выходные данные:
Необходимо вывести на экране в столбик информацию об учениках, у которых сегоня день рождения.
Формат вывода 
 <Фамилия-слово без пробела> <Имя-слово без пробела> <Отчество-слово без пробела>
Фамилии выводить в порядке следования исходных данных
Далее после списка учеников вывести одно число - количество учеников

Известна информация об N (0<N<=100) сотрудниках фирмы: фамилия, имя, отчество, адрес и дата поступления на работу (месяц, год)
Написать программу, организующую ввод исходных данных в структуру и вывести на экран фамилию, имя и адрес сотрудников, которые на сегодняшний день проработали в фирме не менее Z лет

Входные данные: 
В первой строке вводится число N - количество записей
Далее идут N записей в формате (через пробел): <Фамилия-слово без пробела> <Имя-слово без пробела> <Отчество-слово без пробела> <Адрес-слово без пробела> <Месяц поступления - число от 1 до 12> <Год поступления-число>
Далее идет строка с сегодняшней датой в формате  <Месяц - число от 1 до 12> <Год -число>
Далее идет значение Z (0<Z<=10) - количество проработанных лет

Выходные данные:
Необходимо вывести на экране в столбик информацию о сотрудниках, проработавших в фирме не менее Z лет.
Формат вывода 
 <Фамилия-слово без пробела> <Имя-слово без пробела> <Отчество-слово без пробела> <Адрес-слово без пробела> 
Фамилии выводить в порядке следования исходных данных

Даны названия 26 городов и стран, в которыз они находятся. Среди них есть города, находящиеся в разных странах. 
Написать программу, которая организовывает ввод исходных данных в структуру и вывести названия городов  и их количество, находящихся в заданной стране.

Входные данные: 
в первой строке задается название страны
далее идут 26 строк в формате <Страна> <Город>


Выходные данные:
Необходимо вывести все города, которые находятся в стране, указанной в первой строке входных данных.
Каждый город выводить с новой строки
Сразу после списка городов вывести их количество (одно целое число)

Дана строка, представляющая собой адрес URL. Части URL разделяются знаком / или //. 
Необходимо разобрать строку URL на части и вывести каждую часть с новой строки.

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

Выходные данные
Необходимо вывести каждую часть URL адреса с новой строки.
 

Примеры

№	Входные данные	Выходные данные
1	C:/Photo/2013/Pokhod/vasya.jpg	C: Photo 2013 Pokhod vasya.jpg
2	http://chelyabinsk.74.ru/text/newsline/258041618673664.html	http: chelyabinsk.74.ru text newsline 258041618673664.html

 

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


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

Выходные данные: необходимо вывести самое длинное слово и количество символов в нем. Если таких слов несколько, то вывести первое из них.
 

Примеры

№	Входные данные	Выходные данные
1	Vasja      poshel           guljat	poshel 6

Ввести с клавиатуры символьную строку и заменить в ней все буквы «a» на «b» и все буквы «b» на «a» (заглавные на заглавные, строчные на строчные).

Входные данные
В первой строке задается строка без пробелов.

Выходные данные
Необходимо вывести модифицированную строку.
 

Примеры

№	Входные данные	Выходные данные
1	aabbAABBccCC	bbaaBBAAccCC

Герцог Циклонский, обладая безграничным могуществом, что отражено в его девизе "Все могу!", ежегодно проводит конкурс среди приглашенных на исполнение самого заветного желания.
Отбор проводится следующим образом: все претенденты рассаживаются на пронумерованных стульях (нумерация стульев начинается с 1) вокруг Большого Круглого стола, после чего посредством Константы счета начинается отсчет по часовой стрелке.
Претендент, на которого падает Константы счета, обязан освободить место, отсчет продолжается до тех пор, пока не останется два человека. 
Требуется при известном числе гостей N и Константы счета С определить номера стульев, которые нужно занять, чтобы попасть в число этих двух "счастливчиков".

Входные данные
В первой строке вводится число N (\(1<=N<=100\))  - количество приглашенных претендентов. Во второй строке вводится Константы счета (\(С<=100\)).

Выходные данные
Необходимо вывести через пробел два числа - номера стульев "счастливчиков".
 

Примеры

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

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

Входные данные
В первой строке вводится значение N - натуральное число (\(N<=100\)). Во второй строке, вводится N чисел - вес толстяков (от 90 до 150). В третьей строке вводится натуральное число R (\(0<=R<=100\)).

Выходные данные
Вывести в первой строке исходное положение толстяков (их вес, начиная с сидящего на первом стуле):
before: вес толстяков 
Во второй строке вывести положение толстяков через R часов:
after: вес толстяков 
 

Примеры

№	Входные данные	Выходные данные
1	5 98 127 139 141 107  3	before: 98 127 139 141 107  after: 139 141 107 98 127