Информатика

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы – время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Пример организации данных в файле:

ID процесса B	Время выполнения процесса B (мс)	ID процесса(ов) A
1	4	0
2	3	0
3	1	1; 2
4	7	3

 
Процессы с ID = 106 и ID = 113 используют один и тот же ресурс, поэтому не могут выполняться одновременно. Определите минимальное время, через которое завершится выполнение всей совокупности процессов.

Напишите программу для решения следующей задачи.
На контрольной работе по алгебре ученикам 9 класса было предложено 10 примеров. Неудовлетворительная оценка выставляется, если правильно решено менее половины примеров. Сколько неудовлетворительных оценок было получено учениками? Если хотя бы один из учеников правильно решил все задачи, выведите YES, иначе выведите NO.
Программа получает на вход количество учеников в классе N (1 ≤ N ≤ 30), затем для каждого ученика вводится количество правильно решённых примеров.

 

Напишите программу, которая в последовательности натуральных чисел вычисляет сумму всех однозначных чисел, кратных 3. Программа получает на вход натуральные числа, количество введённых чисел неизвестно, 
последовательность чисел заканчивается числом 0 (0 – признак окончания ввода, не входит в последовательность).
Количество чисел не превышает 100. Введённые числа не превышают 300.
Программа должна вывести одно число: сумму всех однозначных чисел, кратных 3.

 

Напишите программу, которая в последовательности натуральных чисел вычисляет сумму всех двузначных чисел, кратных 8. Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 – признак окончания ввода, не входит в последовательность).
Количество чисел не превышает 20. Введённые числа не превышают 1500.
Программа должна вывести одно число: сумму всех двузначных чисел, кратных 8.

 

Напишите программу, которая в последовательности натуральных чисел определяет количество чисел, оканчивающихся на 9. Программа получает на вход количество чисел в последовательности, а затем сами числа. 
В последовательности всегда имеется число, оканчивающееся на 9.
Количество чисел не превышает 1000. Введённые числа по модулю не превышают 30 000.
Программа должна вывести одно число: количество чисел, оканчивающихся на 9
 

Напишите программу, которая в последовательности натуральных чисел определяет сумму чисел, оканчивающихся на 8. Программа получает на вход количество чисел в последовательности, а затем сами числа. 
В последовательности всегда имеется число, оканчивающееся на 8.
Количество чисел не превышает 100. Введённые числа по модулю не превышают 300.
Программа должна вывести одно число: сумму чисел, оканчивающихся на 8.
 

Напишите программу, которая в последовательности натуральных чисел находит среднее арифметическое двузначных чисел, или сообщает, что таких чисел нет (выводит «NO»). Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 – признак окончания ввода, не входит в последовательность).
Количество чисел не превышает 100. Введённые числа не превышают 300.
Программа должна вывести среднее арифметическое чисел, кратных 8, или вывести «NO», если таких чисел нет. Значение выводить с точностью до десятых.
 

Напишите программу, которая в последовательности натуральных чисел находит среднее арифметическое чисел, кратных 8, или сообщает, что таких чисел нет (выводит «NO»). Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 – признак окончания ввода, не входит в последовательность).
Количество чисел не превышает 100. Введённые числа не превышают 300.
Программа должна вывести среднее арифметическое чисел, кратных 8, или вывести «NO», если таких чисел нет. Значение выводить с точностью до десятых.
 

Напишите программу, которая в последовательности натуральных чисел определяет минимальное число, оканчивающееся на 4. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, оканчивающееся на 4. Количество чисел не превышает 1000. Введённые числа не превышают 30 000. Программа должна вывести одно число – минимальное число, оканчивающееся на 4.

Пример работы программы:

Входные данные	Выходные данные
4 24 14 34 10	14

В поле ввода ответа вставьте текст программы и прикрепите файл с исходным кодом

 Напишите программу, которая в последовательности натуральных чисел определяет максимальное число, кратное 5. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 5. Количество чисел не превышает 1000. Введённые числа не превышают 30 000. Программа должна вывести одно число – максимальное число, кратное 5.

Пример работы программы:

Входные данные	Выходные данные
3 10 25 12	25

В поле ввода ответа вставьте текст программы и прикрепите файл с исходным кодом
 

Напишите программу, которая в последовательности натуральных чисел находит среднее арифметическое чисел, кратных 8, или сообщает, что таких чисел нет (выводит «NO»). Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 – признак окончания ввода, не входит в последовательность).
Количество чисел не превышает 100. Введённые числа не превышают 300.
Программа должна вывести среднее арифметическое чисел, кратных 8, или вывести «NO», если таких чисел нет. Значение выводить с точностью до десятых.

Пример работы программы:

Входные данные	Выходные данные
8 122 64 16 0	29.3
111 1 0	NO

 

Напишите программу, которая в последовательности натуральных чисел находит среднее арифметическое двузначных чисел или сообщает, что таких чисел нет (выводит «NO»). Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 – признак окончания ввода, не входит в последовательность).
Количество чисел не превышает 100. Введённые числа не превышают 300.
Программа должна вывести среднее арифметическое двузначных чисел или вывести «NO», если таких чисел нет. Значение выводить с точностью до десятых.

Пример работы программы:

Входные данные	Выходные данные
10 120 49 0	29.5
111 1 0	NO

 

Город Летовецк славится своими туристическими маршрутами. Каждый маршрут проходит через несколько достопримечательностей. Многие туристы желают посетить город, но не у всех хватает времени увидеть все достопримечательности. Туристам предлагают составить список достопримечательностей, которые они бы хотели посетить. Турагент в ответ выбирает для них самый короткий маршрут, включающий все выбранные достопримечательности. 
В последнее время туристов стало так много, что турагент не успевает анализирвать маршруты. Помогите автоматизировать работу турагента, чтобы туристы не теряли времени в ожидании своего маршрута! 

Формат входных данных
В первой строке вводится натуральное число n - количество туристических маршрутов в городе (1 <= n <= 10⁵). Во следующих n строках вводятся сами маршруты. Каждая строка с маршрутов представляет собой список достопримечательностей (слов), разделенных одним пробелом. Количество достопримечательностей в каждой строке не превышает 10⁹. Каждая достопримечательность записана в виде отдельного слова, состоящего только из английских букв и/или цифр.
Последняя строка содержит список достопримечетельностей, которые хочет увитеть турист.  Формат этой строки такой же как и в строках выше.
Гарантируется, что самый короткий подходящий маршрут существует и он единственный.

Формат выходных данных
Выведите самый короткий маршрут, включающий все выбранные туристом достопримечательности. Строка с маршрутом должна соответствовать какой-либо одной строке из входных данных.

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

У друзей есть \(n\) слов одинаковой длины. Они хотят выбрать такое наибольшее число \(k\), чтобы можно было разбить слова на пары так, чтобы в каждой паре у слов совпадало хотя бы \(k\) первых букв.

Помогите друзьям найти искомое максимальное значение \(k\).

Формат входных данных
В первой строке входных данных находится целое число \(n\) — количество слов (\(1 \leqslant n \leqslant 2\cdot 10^5\), \(n\) — четное).

В следующих \(n\) строках заданы слова, которые есть у друзей. Гарантируется, что все строки имеют одинаковую длину и суммарная длина строк не превышает \(2 \cdot 10^6\).

Формат выходных данных
В единственной строке выведите число \(k\) — искомое максимальное значение.

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

Центральная площадь Зожбурга представляет собой прямоугольник, разделенный на одинаковые единичные квадраты. Строки пронумерованы сверху вниз с единицы, столбцы слева направо с единицы. Каждый квадрат площади имеет координаты \(r\) и \(c\) — номер строки и столбца, соответственно.

На площади находится прямоугольный газон со сторонами, параллельными сторонам площади. Координаты левого верхнего углового квадрата газона \((R_L, C_L)\), координаты правого нижнего углового квадрата газона \((R_R, C_R)\). Вокруг газона оборудованы \(n\) дорожек для \(n\) бегунов. Дорожка \(i\) находится на расстоянии \(i\) от границы газона, на дорожке \(i\) находится бегун с номером \(i\). Бегун \(i\) стартует с квадрата с координатами \((r_i, c_i)\). Бегуны стартуют одновременно с одинаковой скоростью: через каждую секунду каждый спорстмен меняет текущий квадрат на своей дорожке на следующий квадрат на своей дорожке в направлении против часовой стрелки.

На прямоугольном газоне в квадрате \((R_p, C_p)\) стоит фотограф, цель которого — сделать красивую фотографию. Фотограф тестирует инновационную камеру с двойным объективом. Эта камера делает снимок одновременно в двух противоположных направлениях. Фотограф считает фотографию красивой, если все бегуны в момент, когда он делает снимок, находятся в одновременно в строке \(R_p\) или в стоблце \(C_p\). При этом благодаря инновационному свойству камеры они могут быть либо в одной строке с ним и справа и слева от него, либо в одном столбце с фотографом и выше и ниже него.

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

Формат входных данных
В первой строке входных данных находится число \(n\) (\(1 \le n \le 18\)) — количество бегунов. В следующей строке ввода даны шесть целых чисел \(R_L\), \(C_L\), \(R_R\), \(C_R\) (\(n + 1 \le R_L \le R_R \le 100 - n\), \(n + 1 \le C_L \le C_R \le 100 - n\)), \(R_p\) (\(R_L \le R_p \le R_R\)), \(C_p\) (\(C_L \le C_p \le C_R\)) — координаты левого верхнего квадрата газона, правого нижнего квадрата газона, координаты фотографа, соответственно. Гарантируется, что \(R_R - R_L + C_R - C_L\) делится на \(4\).

В следующих \(n\) строках даны два числа \(r_i\), \(c_i\) — стартовые координаты бегуна \(i\). Гарантируется, что стартовые координаты бегуна \(i\) находятся на дорожке \(i\), на каждой дорожке находится один бегун, дорожка \(i\) находится на расстоянии \(i\) от границы газона.

Формат выходных данных
Выведите единственное число \(t\) — через какое минимальное количество секунд \(t\) после старта забега фотограф сможет сделать красивую фотографию, или \(-1\), если фотографию сделать не получится.

Рисунок ко второму примеру.

Недавно в город приехал известный цирк. Всего в этом цирке \(n\) акробатов, и в этот раз в честь проведения СПбКОШП 2022 они подготовили особенный номер.

Известно, что \(i\)-й акробат имеет рост \(a_i\) и вес \(b_i\). Любые три акробата могут собраться вместе и показать необычный трюк. Если трюк показывают акробаты с номерами \(i\), \(j\) и \(k\), то эффектность трюка оценивается как \(a_i b_j + a_j b_k + a_k b_i\).

Тренер акробатов считает упорядоченную тройку акробатов \((i, j, k)\) хорошей, если эффектность их трюка будет не меньше, чем если они расположатся в обратном порядке \((k, j, i)\).

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

Формат входных данных
В первой строке ввода дано целое число \(n\) — количество акробатов в цирке (\(3 \leqslant n \leqslant 1000\)).

В \(i\)-й из следующих \(n\) строк через пробел даны целые числа \(a_i\) и \(b_i\) — рост и вес \(i\)-го акробата (\(1 \leqslant a_i, b_i \leqslant 10^9\)).

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

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

Рассмотрим отрезок целых неотрицательных чисел от \(l\) до \(r\). Запишем их подряд в десятичной системе счисления, получив строку \(a\). Например, если \(l=3\), \(r=10\), то \(a=345678910\).

Найдите такой отрезок подряд идущих неотрицательных чисел \([l,r]\) (\(0 \le l \le r \le 10^{18}\)), что записанная для него строка \(a\) имеет длину ровно \(S\), а количество чисел на отрезке \([l,r]\) максимально.

Формат входных данных
Первая строка содержит одно целое число \(S\) (\(1 \le S \le 10^{18}\)).

Формат выходных данных
В первой строке выведите длину отрезка \([l,r]\). Если решения не существует, выведите одно целое число \(-1\).

Если решение существует, во второй строке выведите искомые границы отрезка \(l\) и \(r\).

Если существуют несколько решений, выведите любое из них.