Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Замена чисел#38996

В наборе чисел N замените одно число на число из набора чисел M таким образом, чтобы сумма чисел в наборе N была как можно ближе к числу S. Выведите три числа, каждое в отдельной строке:
1 строка - число, которое заменили из набора N;
2 строка - число из набора M, которым заменили;
3 строка - полученную сумму чисел из набора N.
Гарантируется, что такую замену сделать можно. Если возможных замен несколько, то выбрать ту, в которой число из набора N меньше.

Входные данные
В первой строке вводится через пробел 3 числа: n (10<=N<=10⁵) - количество чисел в наборе N, m (10<=M<=10⁵) - количество чисел в наборе M, S (10<=S<=10⁹) S>sum(N), где sum(N) - сумма всех чисел набора N.
Во второй строке записан набор чисел N: n чисел, разделенных одним пробелом (каждое число по модулю не превышает 10⁵).
Во третьей строке записан набор чисел M: m чисел, разделенных одним пробелом (каждое число по модулю не превышает 10⁵).

Выходные данные
Выведите на экран ответ на задачу, как указано в условии.

Примеры

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

ЕГЭ_информатика Использование сортировки

✓ 32✗ 186900средняяВойти и решать

Количество чисел с суммой не больше S#38995

В файле записаны целые положительные числа. В первой строке файла записано число N - количество чисел, и натуральное число S. В следующих N строках записаны сами числа.
Укажите в ответе два числа через пробел: сначала максимальное количество чисел, которые необходимо сложить, чтобы сумма была не больше числа S, затем, значение полученной суммы.

ЕГЭ_информатика Использование сортировки

1 100труднаяВойти и решать

Хранение данных и сортировка#38994

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

Файл к заданию

Алгоритмы сортировки ЕГЭ_информатика

1 000средняяВойти и решать

Поиск подотрезка массива с максимальной суммой#38942

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

Динамическое программирование: один параметр Префиксные суммы(минимумы, ...)

✓ 0✗ 1—Войти и решать

До Нового года - 1#38928

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

Входные данные
Входная строка содержит два целых числа N и K (\(1<=N<=1000\), \(2<=K<=1000\)).

Выходные данные
Выведите на экран ответ на задачу. Гарантируется, что верный ответ не превышает \(2^{31}-1\).

Примеры

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

Комбинаторика Циклы

✓ 59✗ 251800средняяВойти и решать

До Нового года - 2!#38923

В каком-то другом мире сегодня 30 декабря. В саду деда Коковани посажено N деревьев. Высота i-го дерева (1 <= i <= N) равна h_i метров. Он решает выбрать из этих деревьев K деревьев и украсить их гирляндой. Чтобы декорации были красивее, высота украшенных деревьев должна быть как можно ближе друг к другу. Более конкретно, пусть высота самого высокого украшенного дерева будет h_max метров, а высота самого низкого декорированного дерева будет h_min метров. Чем меньше значение h_max-h_min, тем лучше. Определите минимально возможное значение h_max-h_min?

Входные данные
В первой строке записаны через пробел два числа N и K (2 <= N, K <= 10⁵). В следующих N строках записаны целые числа h_i (1 <= h_i <= 10⁹), по одному в строке.

Выходные данные
Выведите на экран ответ на задачу.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 3 10 15 11 14 12	2	Если украсить первое, третье и пятое деревья, `h_max=12, h_min=10, h_max-h_min=2`.
2	5 3 5 7 5 7 7	0

Алгоритмы сортировки

✓ 51✗ 112800средняяВойти и решать

Эквивалентные строки#38878

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

Входные данные
Первая строка содержит два целых числа k и n — количество используемых букв и количество пар коммутирующих букв (2 ≤ k ≤ 10, 0 ≤ n ≤ k(k − 1)/2).
Следующие n строк содержат по две буквы, не разделенные пробелом: пары коммутирующих букв. Гарантируется, что каждая пара приведена во вводе не более одного раза.
Следующие две строки содержат строки s и t, они имеют равную длину L (1 ≤ L ≤ 100 000) и состоят из первых k букв латинского алфавита.

Выходные данные
Выведите «YES», если строку t можно получить из строки s описанными операциями.
В противном случае выведите «NO».

Примеры

№	Входные данные	Выходные данные
1	3 2 ab bc abbcabc abcacbb	YES
2	3 2 ab bc abbcabc aabbbcc	NO

Алгоритмы на строках графы

✓ 5✗ 101 000средняяВойти и решать

НОД на множестве чисел#38877

Наибольшим общим делителем непустого набора натуральных чисел 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

НОД и алгоритм Евклида

✓ 149✗ 966900средняяВойти и решать

Без неподвижных точек#38876

Перестановкой 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

Перестановки

✓ 6✗ 311 000средняяВойти и решать

Спираль#38875

Робот перемещается по клетчатой плоскости и рисует спираль. Исходно он находится в клетке (0, 0) и направлен в сторону увеличения первой координаты.
Далее он действует по следующему алгоритму: совершает d перемещений вперед, затем поворачивает налево и снова делает d перемещений вперед. После этого он поворачивает налево и умножает значение d на k. Затем робот повторяет описанный процесс. Робот останавливается, сделав суммарно ровно n перемещений.
Требуется вывести картинку, на которой отмечены клетки, на которых побывал робот.

Входные данные
На вход подаются целые числа n, d и k (1 ≤ n ≤ 1000, 1 ≤ d ≤ 100, 2 ≤ k ≤ 5).

Выходные данные
Пусть минимальный прямоугольник из клеток, содержащий все посещенные роботом клетки, имеет высоту h и ширину w. На первой строке выведите числа h и w, разделенные пробелом. Следующие h строк должны содержать по w символов, выведите «*» для клетки, посещенной роботом и «.» для не посещенной.

Примеры

№	Входные данные	Выходные данные
1	13 2 2	5 5 ***** ... .** .... *...

Двумерные массивы Задачи на моделирование

✓ 9✗ 221 100средняяВойти и решать

Объединенная армия#38867

Для борьбы с могучими рейнджерами Рита Репульса и Лорд Зедд решили объединить Глиняный и Зедд патрули. Для более эффективного нападения на Энджел Гроув они хотят построить свою армию в две шеренги. Количество солдат в первой шеренге равно количеству солдат во второй.
Рита любит два вопроса:

«Правда ли, что ровно x из твоих соседей из Зедд патруля?»
«Правда ли, что ровно y из твоих соседей из Глиняного патруля?»

Соседями в данном построении являются солдаты слева и справа в той же шеренге, а также солдат, который стоит на той же позиции, но в другой шеренге. Рита выбрала либо один из этих вопросов либо оба, и задала каждому солдату. Всем солдатам были заданы вопросы с одними и теми же значениями x и/или y.
Зордан с помощью своей магической силы все это время наблюдал за процессом построения. Он был очень удивлен тем, что ответы всех солдат были положительными. Однако, он помнит, что солдаты из Зедд патруля всегда говорят правду, а солдаты из Глиняного патруля обязательно солгут хотя бы на один вопрос.
Так как солдаты из Зедд патруля наиболее опасны по мнению Зордана, исходя из ответов, он хочет узнать какое наименьшее и наибольшее количество солдат из Зедд патруля могло быть в объединенной армии. Он обратился к вам за помощью!

Входные данные
В единственной строке входного файла содержатся три целых числа k, x, y — количество солдат в одной шеренге и числа из вопросов (1 ≤ k ≤ 10⁵; -1 ≤ x, y ≤ 3).
Если x = -1, это означает, что Рита не задавала первый вопрос.
Если y = -1, это означает, что Рита не задавала второй вопрос.
Гарантируется, что Рита задала хотя бы один вопрос.

Выходные данные
Если для данных k, x и y не существует ни одного способа построения, выведите -1.
Иначе, первая строка выходного файла должна содержать одно число — наименьшее возможное количество солдат из Зедд патруля в армии.
В следующих двух строках должно содержаться по k символов «0» и «1» — описание шеренг:

«0» означает, что в построении на соответствующей позиции стоит солдат из Глиняного патруля.
«1» — солдат из Зедд патруля.

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

Примеры

№	Входные данные	Выходные данные
1	2 0 -1	2 01 10 2 01 10
2	5 1 2	0 00000 00000 4 01010 01010
3	1 2 2	0 0 0 0 0 0
4	10 0 3	5 0100010010 0001000100 8 0101010100 0010101010

битмаски Динамическое программирование Задача на реализацию

✓ 2✗ 141 100средняяВойти и решать

Мегазорды#38866

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

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

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

Входные данные
В первой строке входного файла заданы числа g, r и b — количество зордов у зеленого, красного и синего рейнджера соответственно (1 ≤ g, r, b ≤ 10⁵).
В следующей строке находится g чисел x_i — номера моделей, которые есть у зеленого рейнджера (0 ≤ x_i ≤ 10⁹).
В следующей строке находится r чисел y_i — номера моделей, которые есть у красного рейнджера (0 ≤ y_i ≤ 10⁹).
В следующей строке находится b чисел z_i — номера моделей, которые есть у синего рейнджера (0 ≤ z_i ≤ 10⁹).

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

Примеры

№	Входные данные	Выходные данные
1	3 3 2 101 11 52 11 23 23 31 13	3

Замечание
Различные мегазорды из первого примера: 101 + 11 + 13, 52 + 23 + 31, 52 + 23 + 31. Последний мегазорд встречается дважды, так как красный ренжер мог взять либо второй, либо третий зорд. Обратите внимание, что собрать мегазорд 11+11+13 нельзя, так как при этом одна и та же модель будет использована дважны.

Вывод формулы Задачи на моделирование

✓ 3✗ 36900средняяВойти и решать

Рейнджеры в автобусе#38865

Не каждый день могучие рейнджеры надевают свои костюмы. Сами посудите: как нелепо они бы смотрелись, скажем, в общественном транспорте, если бы не снимали их!
Это создаёт определённые трудности злодеям, которые хотят выследить их. Вот и сегодня Рита Репульса не может их поймать, потому что не знает, как они выглядят без костюмов.
Рита следит за автобусом, в котором, по её мнению, едет кто-то из рейнджеров. В салоне автобуса n рядов сидений, в каждом из которых по два места — слева и справа от прохода. Ряды пронумерованы от 1 до n, начиная с передней части автобуса. На конечной остановке в автобус по очереди зашли k человек, и Рита знает, кто на какое место сел и в каком порядке. Кроме того, ей известно, как каждый из рейнджеров выбирает себе место, когда заходит в автобус:

Красный рейнджер любит сидеть впереди. Поэтому среди свободных мест он всегда выбирает место в ряду с наименьшим номером. Если же в этом ряду свободно два места, он садится слева от прохода.
Синий рейнджер тоже любит сидеть впереди. Но, в отличие от красного, когда в ряду с наименьшим номером свободно два места, Синий садится справа.
Чёрный рейнджер любит сидеть сзади. Среди свободных мест он всегда выбирает место в ряду с наибольшим номером, а если там свободно два места, то садится слева от прохода.
Жёлтый рейнджер тоже, любит сидеть сзади. Но, в отличие от чёрного, когда в ряду с наибольшим номером свободно два места, жёлтый садится справа.
Розовый рейнджер не имеет никаких предпочтений и может сесть на любое свободное место.

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

Входные данные
В первой строке заданы числа n и k — количество рядов в автобусе и количество пассажиров (1 ≤ n ≤ 10⁹, 1 ≤ k ≤ min(2 · 10⁵, 2n)).
В следующих k строках описаны пассажиры в том порядке, в котором они заходили в автобус.
В i-й из этих строк заданы числа x_i и y_i — место, на которое сел i-й пассажир (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ 2), x_i — это номер ряда, y_i = 1, если это место слева от прохода, и y_i = 2, если справа.
Все места, на которые сели пассажиры, различны.

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

Примеры

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

Замечание

На этой картинке показаны места, на которые садились пассажиры в примере.

Задачи на моделирование Линейные алгоритмы

✓ 2✗ 25900средняяВойти и решать

Закупка болтов и гаек - 04#38863

Магазин производит закупку болтов (bolt), гаек (nut), гвоздей (pin), шайб (shim) и винтов (screw), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	`6 1650 600 screw 750 bolt 750 shim 450 pin 300 nut 150 bolt`	`2 0`

ЕГЭ_информатика Использование сортировки

✓ 2✗ 81 100средняяВойти и решать

Закупка болтов и гаек - 03#38862

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	`6 1650 600 screw 750 bolt 750 nut 450 pin 300 nut 150 bolt`	`2 0`

ЕГЭ_информатика Использование сортировки

✓ 1✗ 71 100средняяВойти и решать

Закупка болтов и гаек - 02#38861

Магазин производит закупку болтов (bolt) и гаек (nut), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:

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

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

Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов и гаек у метизного завода (1 <= N <= 10⁵) и M - сумма выделенных на закупку денег (в рублях) (1 <= M <= 10⁹). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия (bolt - болт, nut - гайка). Все данные в строках отделены одним пробелом.

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

Примеры

№	Входные данные	Выходные данные
1	`6 6500 1500 nut 500 nut 3500 bolt 3000 bolt 2500 nut 1000 bolt`	`2 500`

ЕГЭ_информатика Использование сортировки

✓ 12✗ 1101 100средняяВойти и решать

Закупка болтов и гаек - 01#38860

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

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

Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов и гаек у метизного завода и M - сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия (bolt - болт, nut - гайка). Все данные в строках отделены одним пробелом.

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

Примеры

№	Входные данные	Выходные данные
1	`6 6500 1500 bolt 500 bolt 3500 nut 3000 nut 2500 bolt 1000 nut`	`2 500`

ЕГЭ_информатика Использование сортировки

✓ 33✗ 1481 000средняяВойти и решать

Переключение между окнами#38849

Когда пользователь работает в операционной системе Windows, у него часто запущено несколько приложений. Каждое из приложений работает в отдельном окне. Для переключения между окнами используется комбинация клавиш «Alt+Tab». Эта комбинация делает активным окно, в котором пользователь работал перед тем, как перейти в текущее активное окно.

Чтобы переключиться в другое окно, можно нажать клавишу «Alt» и затем, не отпуская ее, несколько раз нажать клавишу «Tab». Чтобы понять, какое окно станет активным после этого, воспользуемся следующей моделью. Пусть запущено n приложений. Приложения в операционной системе организованы в виде списка и упорядочены по убыванию времени последней активности. То есть приложение, окно которого является активным в настоящий момент – первое в списке, приложение, окно которого было активно перед этим – второе, и т. д.

Если нажать клавишу «Alt» и затем, не отпуская ее, нажать клавишу «Tab» k раз, то активным станет окно приложения, которое находится на (k mod n) + 1-м месте в списке. Здесь a mod b означает остаток от деления a на b. Иными словами, операционная система рассматривает список как циклический, переходя после последнего элемента списка к первому.

При запуске нового приложения оно добавляется в начало списка.

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

Входные данные
В первой строке вводится целое число n – количество действий пользователя ( 1 ≤ n ≤ 1000). Следующие n строк содержат описание действий пользователя.

Запуск приложения описывается строкой «Run <имя приложения»>. Здесь «<имя приложения»> – строка из не более чем 100 латинских букв, цифр и пробелов. Она отделена от слова «Run» ровно одним пробелом. Все имена приложений различны. Большие и маленькие буквы считаются различными.

Переключение между приложениями описывается строкой «Alt+Tab+...+Tab», здесь подстрока «+Tab» повторена в точности столько раз, сколько раз пользователь нажал клавишу «Tab», не отпуская клавишу «Alt». Это количество не превышает 100.

Первая команда во входных данных – всегда команда «Run».

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

Примеры

№	Входные данные	Выходные данные
1	6 Run Mozilla Firefox Run Free Pascal Alt+Tab Run Miranda IM Alt+Tab+Tab Alt+Tab+Tab+Tab	Mozilla Firefox Free Pascal Mozilla Firefox Miranda IM Free Pascal Free Pascal

Задачи на моделирование Список

✓ 68✗ 178900средняяВойти и решать

Кинотеатр#38847

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

НОД и алгоритм Евклида

✓ 170✗ 337600лёгкаяВойти и решать

Коровы#38846

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

Входные данные
В первой строке входного файла записано число досок 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

Потоки

✓ 6✗ 30800средняяВойти и решать