Информатика

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

В рамках подготовки к запуску ГЦД было разработано специальное расписание, содержащее n рейсов в одном направлении и m рейсов в обратном. Для каждого рейса определены a_i - время отправления с первой конечной станции и b_i - время прибытия на вторую конечную станцию, для обратных рейсов c_j - время отправления со второй станции и d_j - время прибытия на первую станцию. Времена измеряются в минутах от начала дня. Внутри большого города поезда могут
передвигаться по различным маршрутам, поэтому поезд, отправившийся позже какого-то другого поезда, может прибыть раньше него.

Проекты такого масштаба ещё не запускались, а значит, будут происходить непредвиденные события и поезда будут задерживаться. Аналитики компании, обслуживающей ГЦД, посчитали, что при любых обстоятельствах поезд может опоздать на конечную станцию не более чем на t минут. Поезд может отправиться выполнять следующий рейс сразу же, как только закончил предыдущий.

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

Формат входных данных
Первая строка входных данных содержит максимальное время задержки при выполнении рейса t, 0 <= t <= 10⁹.
Следующая строка содержит число n - количество рейсов в расписании в одну сторону, 0 <= n <= 100. Следующие 2n строк содержат числа a₁, b₁, a₂, b₂, ..., a_n, b_n - время отправления поездов от первой станции и время их прибытия на вторую станцию, 0 <= a_i < b_i <= 10⁹.
Следующая строка содержит число m - количество поездов в расписании в обратную сторону, 0 <= m <= 100. Следующие 2m строк содержат время отправления c_j и прибытия d_j поездов в обратном направлении в аналогичном формате, 0 <= cj < dj <= 10⁹.
Поезда в расписании перечислены в произвольном порядке, не обязательно в порядке возрастания времени.

Формат выходных данных
Программа должна вывести одно целое число - минимальное количество поездов, необходимое для выполнения данного расписания.

Ввод	Вывод
4 2 3 8 5 10 1 11 15	3
1 2 15 18 7 9 2 11 14 1 3	1

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

Формат входных данных
Первая и вторая строки входных данных содержат по одному числу n и m (3 ≤ n ≤ 2 x 10⁹  , 3 ≤ m ≤ 2 x 10⁹) - размеры площади.
Третья строка содержит количество имеющихся плиток t, 1 ≤ t < nm.
Формат выходных данных
Программа должна вывести единственное число - максимальную ширину дорожки, которую
можно выложить из имеющихся плиток.
 

Ввод	Вывод
6 7 38	2

Замечание
Пояснение к примеру. Площадь имеет размеры 6 х 7, из 38 плиток можно выложить дорожку шириной в 2 плитки.

Некоторые уроки в школе для Вани и Пети  очень скучны. На этих уроках Петя и Ваня придумали игру. Сначала мальчики записывают на листке два различных натуральных числа a и b .
Ход игры заключается в следующем: среди записанных чисел выбирают p и q такие, что модуля их разности \(| p - q |\) еще нет на листке, и дописывают его.
Проигрывает тот, кто не может сделать ход.
Определите, кто из ребят окажется победителем при правильной игре обоих. Ваня вежливый мальчик, поэтому всегда ходит вторым.

Входные данные: В первой и единственной строке записано два различных натуральных числа 1 <= a , b <= 10^9 , разделенные пробелом - два исходных числа на листке.

Выходные данные: Выведите имя победителя в этой игре (Petya или Vanya)

Примечание: В первом примере Петя первым ходом допишет на листок число |6−2| = 4 . Больше ходов нет, поэтому выигрывает Петя. Во втором примере первым ходом на листок будет дописано число |4−1| = 3 . Затем Ваня может записать |3−1| = 2 , тогда у Пети ходов не останется. Побеждает Ваня.

Примеры

№	Входные данные	Выходные данные
1	6 2	Petya
2	4 1	Vanya

Пятиклассники Петя и Ваня изучили на уроках математики следующий алгоритм Евклида:

1. Пусть a, b — числа, НОД которых надо найти.

2. Если b = 0, то число a — искомый НОД.

3. Если b > a, то необходимо поменять местами числа a и b.

4. Присвоить числу a значение a – b.

5. Вернуться к шагу 2.

Маша придумала для них задачу на закрепление. Она попросила мальчиков придумать такие числа a, b, c и d, что в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) наступает такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.

Напишите для Маши программу, которая проверит, удовлетворяют ли числа a, b, c, d условиям Маши.

Входные данные: Первая строка входных данных содержит количество наборов входных данных K (\(1 <= K <= 100\)). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (\(1 <= a,\ b <= 10^{18}\)). Вторая строка – два целых числа: c, d (\(1 <= c,\ d <= 10^{18}\)).
Все числа в строках разделены пробелом.

Выходные данные: Для каждого набора входных данных выведите слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO».

 

Примеры

№	Входные данные	Выходные данные
1	2 20 10 10 10 10 7 2 4	YES NO

 

Дана последовательность N целых положительных чисел, не превышающих 10000. Рассматриваются все пары элементов последовательности, у которых различные остатки от деления на \(D=140\) и, хотя бы одно из чисел, делится на \(C=7\). Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля. .

Входные данные
В первой строке записано натуральное число N (\(2 <= N <= 10000\)) – количество чисел в последовательности. В следующих N cтроках записаны числа, входящие в последовательность, по одному в каждой строке.

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

 

Примеры

№	Входные данные	Выходные данные
1	5  13  14  15  16  17	14 17

Напишите программу, которая в последовательности целых чисел определяет значение наименьшего числа из всех четных введенных чисел. Программа получает на вход целые положительные числа, количество введенных чисел неизвестно, последовательность чисел заканчивается числом 0 (0-признак окончания ввода, не входит в последовательность).
Количество чисел не превышает 1000. Введенные числа не превышают 30 000.  Среди  введенных чисел есть хотя бы одно четное
Программа должна вывести одно число: наименьшее из всех четных введенных чисел

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

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

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

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

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

 В библиотеке на стеллажи расставляют книги. Книги ставятся на полки ровно по  K штук на каждую, если полка не может быть заполнена полностью, она остается пустой. В каждом стеллаже по М полок. Последний стеллаж может быть заполнен не полностью. Всего имеется N книг. Сколько всего понадобится стеллажей, сколько полок будет заполнено на последнем стеллаже и сколько книг останется не выставлено на стеллажи (выставить нужно как можно больше книг)? Написать программу: вводятся три числа целых N, M, K в одной строке; вывести три числа в одной строке - сначала количество потребовавшихся стеллажей, затем количество заполненных книгами полок на последнем стеллаже, а затем количество не выставленных книг
 
Примеры

№	Входные данные	Выходные данные
1	50 70 8	1 6 2

 

 
 

Из цветных лампочек комплектуют новогодние гирлянды. Сначала лампочки связываются в "снежинку" ровно по  K штук в каждой, а потом "снежинки" - в гирлянды, причем каждая гирлянда вмещает не более M "снежинок". Последняя гирлянда (только она одна) может быть короче других (включать в себя меньше "снежинок", чем остальные). Всего имеется N лампочек.  Сколько всего получится гирлянд, сколько "снежинок" будет в последней гирлянде и сколько лампочек останется неиспользованными (нужно использовать как можно больше лампочек)? Написать программу: вводятся три числа целых N, M, K в одной строке; вывести три числа в одной строке - сначала количество получившихся гирлянд, затем количество "снежинок" в последней гирлянде, а затем количество неиспользованных лампочек
 
Примеры

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

В некоторых клетках квадрата \( N\ х\ N\) живут микроорганизмы (не более одного в одной клетке). Каждую секунду происходит следующее:
– все микроорганизмы, у которых менее 2-х соседей, умирают от скуки (соседями называются микроорганизмы, живущие в клетках, имеющих общую сторону или вершину);
– все микроорганизмы, у которых более 3-х соседей, умирают от перенаселенности;
– на всех пустых клетках, у которых ровно в трех соседних клетках жили микроорганизмы, появляются новые микроорганизмы.
Все изменения происходят одновременно, то есть для каждой клетки сначала выясняется ее судьба, а затем происходят изменения сразу во всех клетках.
Требуется по данной конфигурации определить, во что она превратится через \(T\) секунд.

Входные данные: В первой строке вводятся два натуральных числа –\( N\) (\(1 \leq N \leq 10\)) и \(T\) (\(1 \leq T \leq 100\)). Далее записано \( N\) строчек по \( N\) чисел, описывающих начальную конфигурацию (0 – пустая клетка, 1 – микроорганизм). Числа в строках разделены пробелами.
Выходные данные: Требуется вывести \( N\) строк по \( N\) чисел – описание конфигурации через T секунд (в том же формате, как и во входных данных).

Примеры

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

Алина выписала на доске \(n + 1\) цифру, каждая из которых от \(1\) до \(9\). Даша поставила между каждой парой соседних цифр знак одной из арифметических операций <<+>>, <<->>, <<*>> и <</>> (плюс, минус, умножить, целочисленное деление). Затем девочки отправились в столовую на обед.

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

Они просят вас зная последовательность знаков, расставить цифры от \(1\) до \(9\) между ними так, чтобы итоговый результат был максимальным.

Формат входных данных
В первой строке дано число \(n\), число знаков, которые написала Даша (\(1 \le n \le 1000\)).

Во второй строке находится \(n\) знаков арифметических операций <<+>>, <<->>, <<*>> и <</>> (без кавычек).

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

Если возможных решений несколько, разрешается вывести любое.

На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии кратном 5 (разница в индексах элементов пары должна быть кратна 5, порядок элементов в паре не важен). Необходимо определить пару с максимальной суммой кратной 7. Если таких пар несколько, программа должна вывести любую из них.

Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 <= N <= 10000\)). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.

Выходные данные
Программа должна вывести в первой строке два числа: пару элементов с максимальной суммой, находящихся в последовательности на расстоянии кратном 5, в которой сумма элементов кратна 7. Если ни одной подходящей пары нет, нужно вывести одно число 0.

 

Примеры

№	Входные данные	Выходные данные
1	10 1 6 3 140 6 6 7 11 7 15	7 140

На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен). Необходимо определить пару с максимальной разностью, элементы которой находятся на расстоянии кратном K. Если таких пар несколько, вывести любую.

Входных данные
В первой строке входных данных задаётся количество чисел N и значение K (\(K+1 <= N <= 10000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.

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

 

Примеры

№	Входные данные	Выходные данные
1	8 3 1 90 3 81 89 4 71 7	90 7

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых сумма элементов кратна 8.

Входные данные
В первой строке входных данных задаётся количество чисел N (\(5 <= N <= 1000\)). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. 

Выходные данные
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше 4, в которых сумма элементов кратна 8.
 

 

Примеры

№	Входные данные	Выходные данные	Комментарий
1	7  1  5  9  8  15  23  31	4	Найденные пары: (1,15) (1,23) (1,31) (9,31)

Предприятие «Авто-2010» выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.

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

Входные данные
Первая строка входного файла содержит число n (1≤ n ≤ 100000) — количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂, p_n, определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 10⁹ секунд.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-я строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера. В i-й строке нет повторяющихся номеров деталей. Сумма всех чисел k_i не превосходит 200000.

Известно, что не существует циклических зависимостей в производстве деталей.

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

Ввод	Вывод
3 100 200 300 1 2 0 2 2 1	300 2 2 1
2 2 3 1 2 0	5 2 2 1
4 2 3 4 5 2 3 2 1 3 0 2 1 3	9 3 3 2 1

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

Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 <= N <= 10000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.

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

 

Примеры

№	Входные данные	Выходные данные	Комментарий
1	7  1  2  3  9  5  6  7	5	Найденные пары: (1,6) (2,6) (3,5) (3,6) (3,7)

Шифрование - это преобразование информации, делающее ее нечитаемой для посторонних. При этом доверенные лица могут провести дешифрование и прочитать исходную информацию.
Одним из самых известных алгоритмов шифрования является шифр Цезаря. Чтобы зашифровать последовательность, к каждому элементу последовательности прибавляется некоторое целое число. Так, например, из последовательности {1, 2, 3, 4} можно получить последовательность {5, 6, 7, 8} применением шифра Цезаря с ключом «+4».
Вы смогли перехватить две последовательности чисел A и B, которые оказались одинаковой длины. Нужно проверить, могла ли первая из них быть получена из второй применением шифра Цезаря.

Формат входных данных
В первой строке задано одно число n - длина последовательности (1≤n≤1000). Во второй строке находятся n целых чисел a1, a2, ..., an - последовательность A (−10⁴ ≤a_i≤10⁴ ). В третьей строке находятся n целых чисел b1, b2, ..., bn - последовательность B (−10⁴ ≤b_i≤10⁴ ).

Формат выходных данных
Выведите NO, если последовательность A нельзя получить из последовательности B шифром Цезаря, иначе выведите YES, а в следующей строке выведите ключ шифра с учетом знака.

Ввод	Вывод
4 1 2 3 4 5 6 7 8	YES 4
2 1 2 2 1	NO
1 -1 -2	YES -1

 

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

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

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

Входные данные
Первая строка входных данных содержит  число N (2 ≤ N ≤ 50).

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

Выходные данные
Ваша программа должна вывести описание процесса упорядочения.

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

Количество выводимых строк  не должно превышать 50000.

Если требуемого упорядочения колечек достичь не удается,  программа должна вывести одно число –1
 

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