Информатика

Наибольшим общим делителем непустого набора натуральных чисел A называется максимальное натуральное число d, такое что оно является одновременно делителем всех чисел множества A.
Задан массив натуральных чисел [a₁, a₂, . . . , a_n] и число k. Требуется выбрать в нем подмассив из k подряд идущих элементов [a_l, a_l+1, . . . , a_l+k−1], чтобы их наибольший общий делитель был как можно больше, и вывести этот наибольший общий делитель.

Входные данные
Первая строка ввода содержит два целых числа n и k (2 ≤ n ≤ 500 000, 2 ≤ k ≤ n).
Вторая строка содержит n натуральных чисел a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10¹⁸).

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

Примеры

№	Входные данные	Выходные данные
1	10 4 2 3 4 8 12 6 12 18 4 3	6

Перестановкой n элементов называется массив из различных натуральных n чисел, каждое из которых от 1 до n. Например, все перестановки 3 элементов: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].
Элементы перестановки пронумерованы от 1 до n, например для перестановки a = [3, 1, 2] выполнено a[1] = 3, a[2] = 1, a[3] = 2. Элемент с номером i называется неподвижной точкой, если a[i] = i. Так, в перестановке [3, 1, 2] нет неподвижный точек, а в перестановке [1, 3, 2] элемент a[1] = 1 является неподвижной точкой.
Упорядочим все перестановки лексикографически — сначала по первому элементу, потом по второму, и так далее. В начале условия все перестановки трех элементов приведены в лексикографическом порядке. Оставим только те перестановки, которые не содержат неподвижных точек. Для n = 3 останутся перестановки [2, 3, 1] и [3, 1, 2].
По заданным n и t требуется вывести первые t в лексикографическом порядке перестановок n элементов без неподвижных точек. Перестановки следует выводить в лексикографическом порядке.

Входные данные
На ввод подаются два целых числа n и t (2 ≤ n ≤ 1000, 1 ≤ t ≤ 10⁴, nt ≤ 10⁵ ). Гарантируется, что существует хотя бы t перестановок n элементов без неподвижных точек.

Выходные данные
Выведите t строк, на i-й из них выведите n чисел: i-ю в лексикографическом порядке перестановку n элементов без неподвижных точек.

Примеры

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

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

Входные данные
На вход подаётся целое число n (1 ≤ n ≤ 10¹⁸). Обратите внимание, что для хранения такого числа требуется 64-битный тип данных (int64 в паскале, long long в C++).

Выходные данные
Выведите одно число — максимальное число различных квадратов, которое сможет сложить Петя.
 

Примеры

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

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

Входные данные
На вход подаётся три целых числа: w, l и h — длина, ширина и высота комнаты, каждое
на отдельной строке (1000 ≤ w, l, h ≤ 10 000).

Выходные данные
Если комната является хорошей, выведите «good», иначе выведите «bad».
 

Примеры

№	Входные данные	Выходные данные
1	4000 6000 3000	bad
2	4600 8600 1600	good

Марья Ивановна с Марьей Михайловной привели школьников в кинотеатр. Чтобы не было никаких обид, Марья Ивановна построила всех школьников по алфавиту и рассадила их: сначала в первый ряд слева направо, затем во второй слева направо и т.д., заполнив весь зал из n рядов по m кресел. Тут пришла Марья Михайловна и сказала, что ребята сели неправильно – надо пересесть. Она предложила сначала заполнить все первые места от первого ряда к последнему, затем все вторые места и т. д.

Определите, сколько школьников после такой пересадки останется на своем месте.

Например, если n = 3 и m = 3, то в первом случае дети сядут так:

1    2    3
4    5    6
7    8    9
а во втором – так:
1    4    7
2    5    8
3    6    9
Таким образом, три школьника: 1, 5 и 9 останутся на своих местах.

Входные данные
Вводятся два целых числа n и m (1 ≤ n, m ≤ 10⁹ ).

Выходные данные
Выведите количество школьников, которые останутся на своих местах.
 

Примеры

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

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

Входные данные
В первой строке входного файла записано число досок N (0 <= N <= 1000). Далее для каждой доски записаны координаты кочек - концов доски (-2³¹ <= X_i,Y_i <= 2³¹). Затем записаны координаты начальной и конечной точек (точки различны и доски, их соединяющей нет). Все числа во входном файле целые.

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

Примеры

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

Новый премьер-министр решил проехать по России от Москвы до Владивостока по железной дороге, а затем вернуться обратно. Он поручил своим помощникам разработать маршрут так, чтобы не пришлось два раза проезжать через один и тот же город. Однако помощники сообщили, что для Российских железных дорог это невозможно. Определите, в каких городах премьер-министр будет вынужден побывать дважды.

Входные данные
В первой строке входного файла находятся числа N - количество российских городов, соединенных железными дорогами в единую сеть и М - количество железнодорожных перегонов, соединяющих пары городов (1 <= N <= 20000, 1 <= M <= 200000). Города имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя городами проходит соответствующая железнодорожная ветка. В последней строке находятся два целых числа S и Е (1 <= S != E <= N) - номера Москвы и Владивостока по версии РЖД.

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

 
 

Примеры

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

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

Входные данные
В первой строке входного файла находятся числа N - количество площадей в городе и М - количество улиц их соединяющих (1 <= N <= 20000, 1 <= M <= 200000). Площади имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя площадями проходит соответствующая улица (две площади соединяются не более чем одной улицей).

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

 
 

Примеры

№	Входные данные	Выходные данные
1	10 16 2 6 3 7 6 5 5 9 5 4 1 2 9 8 6 4 2 10 3 8 7 9 1 4 2 4 10 5 1 6 6 10	1 4

Маленький мальчик делает бусы. У него есть много пронумерованных бусинок. Каждая бусинка имеет уникальный номер - целое число в диапазоне от 1 до N. Он выкладывает все бусинки на полу и соединяет бусинки между собой произвольным образом так, что замкнутых контуров не образуется. Каждая из бусинок при этом оказывается соединенной с какой-либо другой бусинкой. Требуется определить, какое максимальное количество последовательно соединенных бусинок присутствует в полученной фигуре.

Входные данные
В первой строке записано число N (1 ≤ N ≤ 2500) - количество бусинок . В последующих N - 1 строках по два целых числа - номера, соединенных бусинок.

Выходные данные
Вывести одно число - искомое количество бусинок.
 

Примеры

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

Даны два числа n и m. Создайте двумерный массив размерностью nхm и заполните его по следующему правилу:
- числа, стоящие в строке 0 или в столбце 0 равны 1 (A[0][j]=1, A[i][0]=1);
- значения остальных элементов массива должны быть равны сумме элементов, стоящих на один слобец левее и на одну строку выше от этого элемента. 

Входные данные
Программа получает на вход два числа n и m.

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

Примеры

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

Однажды на дистанционном уроке, проводимом при помощи какого-то сервиса видеоконференций, учитель заметил, что отсутствует один из N учащихся класса. Чтобы понять, кто именно отсутствует, учитель попросил каждого присутствующего ученика написать в чат его номер в классном журнале: число от 1 до N. Тогда после окончания урока, просмотрев сохранённый чат, учитель сможет понять, какой из учеников не написал свой номер. Помогите ему - напишите программу, которая сделает это.

Входные данные
В первой строке входных данных записано целое число N (1 <= N <= 10⁵ ) — количество учеников в классе. Следующие N-1 строк содержат по одному числу — номера присутствовавших на уроке учеников в произвольном порядке. Среди этих чисел каждое число от 1 до N, кроме какого-то одного, встречается ровно один раз.

Выходные данные
Программа должна вывести одно число — номер отсутствовавшего ученика.
 

Примеры

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

Спелестологический клуб «Залезь и посмотри» часто привлекается к поиску заблудившихся в каменоломнях незадачливых путешественников. Заблудившиеся в темноте и тесноте паникуют, хаотично перемещаются, ходят кругами и осложняют этим поисковые работы. Гораздо удобнее было бы, если бы потерявшиеся сидели в каком-нибудь зале и никуда не двигались.
Каменоломни представляют собой набор из N залов, занумерованных числами от 1 до N и M проходов между ними. Проходы могут быть как двусторонними, так и односторонними (например, с сильным вертикальным уклоном). Ни один проход не соединяет зал сам с собой. Пара залов может соединяться максимум одним проходом. Гарантируется, что двигаясь только по односторонним проходам, нельзя попасть в тот зал, из которого вышли путешественники.
Чтобы избежать хождения заблудившихся по кругу, члены клуба решили нанести на двусторонние проходы специальные аварийные стрелки так, чтобы идя по этим стрелкам нельзя было попасть в уже посещенное место, откуда бы ни началось движение и, в итоге, потерявшиеся оказались бы в одном из залов, из которого нельзя уйти, двигаясь по стрелочкам — там их и найдут спелестологи.
Для каждого двустороннего прохода определите допустимое направление движения.

Формат входных данных
В первой строке входных данных задается два числа N (2 ≤ N ≤ 100000) и M (1 ≤ M ≤ 100000) — количество залов и проходов между ними.
В следующих M строках задаются описания проходов. Каждое описание состоит из трёх чисел A, B и D (1 ≤ A, B ≤ N). Числа A и B задают номера соединенных проходом залов. Если D = 1, то проход односторонний из зала A в зал B. Если D = 2, то проход двусторонний.

Формат выходных данных
Для каждого двустороннего прохода из входных данных выведите пару чисел, описывающих соединяемые этим проходом залы. Движение может осуществляться из первого зала во второй.
Если правильных ответов несколько — выведите любой из них. Порядок вывода описания проходов не важен. Гарантируется, что ответ всегда существует.
 
 

Примеры

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

Даны два числа n и m. Создайте двумерный массив A[n][m], заполните его таблицей умножения A[i][j]=i*j и выведите на экран. При этом нельзя использовать вложенные циклы, все заполнение массива должно производиться одним циклом.
Входные данные
Программа получает на вход два числа n и m – количество строк и столбцов, соответственно.

Выходные данные
Программа должна вывести  полученный массив. Числа разделяйте одним пробелом.
 

Примеры

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

Склиссы — "сумчатые парнокопытные" в виде коровы с перепончатыми крыльями с планеты Шешинеру. Несмотря на способность летать, склисс, как и любая земная корова, достаточно ленива и тугодумна (почитайте побольше про склиссов ). 
Профессор Игорь Селезнев взял на борт трех склиссов для изучения: Бесси (Bessie), Элси (Elsie) и Милдред (Mildred), каждая из которых изначально дает 7 галлонов молока в день. Поскольку известно, что надой склисса со временем может измениться, профессор Селезнев проводит периодические измерения в течение следующих 100 дней и записывает их в журнал. Записи в его журнале выглядят так:

35 Bessie -2
14 Mildred +3

Первая запись указывает на то, что на 35-й день надой Бесси был на 2 галлона ниже, чем при последнем измерении. Следующая запись указывает, что на 14-й день надой молока у Милдред увеличился на 3 галлона по сравнению с тем, когда он был измерен в последний раз.
Профессор Селезнев занят во многих исследованиях, поэтому он может сделать не более одного измерения в день. К сожалению, он не всегда успевает сразу записать все в журнал и, поэтому его измерения могут идти не в хронологическом порядке.

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

Входные данные
Первая строка ввода содержит N, количество измерений, которые сделал профессор. Каждая из последуюших N строк описывает одно измерение, в формате, описанном выше: день (целое число от 1 до 100), имя склисса, и изменение производительности (ненулевое целое число). Количество молока, которое даёт любой склисс, всегда будет в интервале 0..1000.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 7 Mildred +3 4 Elsie -1 9 Mildred -1 1 Bessie +2	3	Иначально все склиссы дают по 7. В день 1 производительность Бесси вырастет до 9, делая её единственной победительницей и вынуждающей профессора сменить фотографию. В день 4 производительность Элси уменьшится до 6, но это не изменит того факта, что лидером останется Бэсси. В день 7 Милдред выйдет в лидеры, в день 8 Милдред сравняется с Бесси, что опять приведёт к смене карточек.

Аборигены с планеты Шешинера очень любят земные ананасы. Побывав у них в гостях, Алиса решила отправить несколько штук им в подарок. На то, чтобы доставить ананасы свежими есть всего 24 часа.

Алиса хочет хочет отправить как можно большее число ананасов. Капитан Полосков решил ей помочь и с радостью согласился слетать на своем космическом корабле. Но есть один нюанс: на некоторых космических маршрутах можно дозаправить корабль, не превышающий максимально установленный вес. А заправлять корабль в пути нужно всегда, иначе он просто не долетит. Поэтому если корабль заполнить ананасами по максимуму, то, его не получится дозаправить в пути и поэтому не удастся воспользоваться самым коротким маршрутов, и придётся лететь через другие планеты. Может случиться даже так, что корабль не успеет долететь до Шешинеры вовремя, и ананасы испортятся. 
Итак, сколько же ананасов можно погрузить в космический корабль, чтобы доставить груз вовремя?

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

Планеты нумеруются числами от 1 до n. Планеты Земля имеет номер 1, а планета Шешинера - номер n. Время перелета по маршруту задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что один ананас весит 100 грамм, а пустой корабль -  3 тонны.

Выходные данные
Выведите одно число - максимальное количество ананасов, которое можно доставить, потратив не более 24часов.
 

Примеры

№	Входные данные	Выходные данные
1	3 3 1 2 10 3000220 2 3 20 3000201 1 3 1 3000099	2

Беззработный Дэйв от скуки  соорудил в собственной гостиной лабиринт из картонных коробок. Лабиринт содержит  K входов. Когда его подружка Энни вернулась, лабиринт невероятным образом разросся изнутри, а сам горе-изобретатель там заблудился и не может выбраться.
Единственное, что нашла Энни в комнате это карту лабиринта, который имеет размеры NхM клеток. На карте было обозначено место, в котором находится Дэйв (как так вышло никто не знает). Клетки лабиринта либо пустые, по которым можно пройти, либо в них находится стена и по ним проходить нельзя. У клетки может быть до 4-х смежных клеток, в которую можно пройти из текущей.
Энни пригласила вас помочь ей определить, с какого входа нужно начать свой путь, чтобы побыстрее дойти до Дейва. Если таких входов несколько, Энни пойдет со входа с наименьшим номером.

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

Программа получает на вход несколько строк. В первой строке - 2 числа N и M (1<= N, M <= 100, NxM <= 100), размеры лабиринта. Далее следует N строк по M символов в каждой - описание лабиринта. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с Дэйвом.
В (N+2)-й строке находится число K (1<=K<=NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. В i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в xi-й строке и в yi-м столбце (1<=xi<=N,1<=yi<=M).
Координаты входов попарно различны, все входы расположены в пустых клетках. Ни один из входов не находится в клетке с Дэйвом.

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

Выведите одно число - номер входа (нумерация начинается с 1). Если до Дэйва невозможно добраться, выведите -1.
 

 

Примеры

№	Входные данные	Выходные данные
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	1
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

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

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

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

В первой строке входного файла записаны числа N и M – размеры лабиринта (целые положительные числа, не превышающие 100). Затем идет N строк по M чисел в каждой – описание лабиринта. Число 0 в описании означает свободное место, число 1 – препятствие, число 2 – отверстие.

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

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

 

Примеры

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

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

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

Пример организации исходных данных во входном файле:
7
21
13
9
19
17
26
95
В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Для указанных программа должна вывести число 2.

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

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

Примеры

№	Входные данные	Выходные данные
1	33251	1 8