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

Переключая каналы#60951

Родители Лизы подключили пакет, содержащий N телевизионных каналов, пронумерованных числами от 1 до N. Переключать каналы можно с помощью двух кнопок на пульте: «+» и «−». Короткое нажатие на кнопку «+» приведёт к переключению на следующий канал, если номер текущего канала меньше N; если же номер текущего канала равен N, то телевизор продолжит показывать этот канал. Если кнопку «+» нажать и удерживать некоторое время, произойдёт переход на K каналов вперёд, при условии, что номер текущего канала не превосходит N − K. В противном случае произойдёт переход на канал N.
Аналогично, короткое нажатие на кнопку «−» приведёт к переключению на предыдущий канал, если номер текущего канала больше 1; если же номер текущего канала равен 1, телевизор продолжит показывать этот канал. Если кнопку «−» нажать и удерживать некоторое время, то произойдёт переход на K каналов назад при условии, что номер текущего канала превышает K. В противном случае произойдёт переход на канал 1.
Лиза включила телевизор и обнаружил, что он показывает канал P. Лиза знает, что очень скоро по каналу с номером U начнётся интересная передача. Определите, какое минимальное количество нажатий на кнопки пульта потребуется сделать Лизе, чтобы переключиться на канал U.
Формат входных данных
В первой строке содержится целое число N (3 ≤ N ≤ 10⁹ ) — количество телевизионных каналов.
Во второй строке содержится целое число K (2 ≤ K < N) — количество каналов, на которое осуществится переход назад или вперёд при удерживании соответствующей кнопки переключения.
В третьей строке содержится целое число P (1 ≤ P ≤ N) — номер канала, который показывает телевизор.
В четвёртой строке содержится целое число U (1 ≤ U ≤ N) — номер канала, на который желает переключиться Лиза. Гарантируется, что P = U.
Формат выходных данных
Выведите одно целое неотрицательное число — минимальное количество нажатий на кнопки пульта, которое необходимо для переключения с канала P на канал U.

Замечание
В первом примере Лизе следует сначала выполнить одно короткое нажатие на кнопку «+» и переключиться с канала 3 на канал 4, а затем трижды осуществить переход вперёд на 5 каналов: сначала переключиться с 4 на 9, затем с 9 на 14 и, наконец, с 14 на 19 канал.
Во втором примере Лиза может сначала переключиться коротким нажатием на кнопку «−» на канал 2, после чего выполнить три перехода вперёд на 5 каналов: с канала 2 на канал 7, затем на канал 12 и, наконец, на канал 17.
В третьем примере Лиза дважды выполнит короткое нажатие кнопки «−».
В четвёртом примере Лизе нужно сначала перейти назад, на канал 1, после чего трижды выполнить переход вперёд, последовательно на каналы 6, 11, 16.

Линейные алгоритмы Разбор случаев

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

Порядок во всём#60129

Вася — очень порядочный мальчик, он любит порядок во всём.

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

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

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(2 \le n \le 3 \cdot 10^{5}\)) — количество чисел в тетрадке у Васи.

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

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

Примечание

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

Во втором примере Васе можно приписать ко второму числу цифру 3, тогда числа станут равны 13, а значит, будут расположены по неубыванию. При этом 13 — это минимально возможное последнее число.

В третьем примере Вася может, например, получить числа 20, 25, 100. Возможны и другие варианты, но последнее число при любом способе дописывания цифр получится не меньше 100.

Задача на реализацию Разбор случаев

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

Фестиваль чисел#59883

В городе Летовецк "Фестиваль Чисел" отмечается всегда в день с магической датой. Дата называется магической, если день, номер месяца и две последние цифры года совпадают. Например, 01.01.01 - магическая дата.
По текущей дате, записанной в формате дд.мм.гг определите дату, когда будет отмечатся ближайший "Фестиваль чисел". То есть первую магическую дату, которая была бы не ранее текущей.

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

Формат выходных данных
Программа должна вывести ближайшую дату "Фестиваля чисел" в формате дд.мм.гг.

Задачи на моделирование Разбор случаев

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

Сломанный индикатор#50944

У радиолюбителя Алексея есть девятисегментный жидкокристаллический индикатор, который может показывать цифры от \(0\) до \(9\) в виде цифр <<почтового индекса>> (см. рисунок):

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

Алексей уже выяснил, что индикатор всё ещё способен показать какие-то \(n\) цифр. Однако радиолюбитель не может проверить остальные цифры, равно как и каждый сегмент отдельно. Поэтому он просит вас помочь найти те цифры, которые гарантированно можно показать на этом индикаторе.

Формат входных данных
Первая строка входных данных содержит число \(n\) (\(1 \le n \le 10\)) — количество цифр, которые смог показать на индикаторе Алексей.

Следующие \(n\) строк содержат по одной цифре \(a_i\) (\(0 \le a_i \le 9\)) — сами цифры, которые Алексей смог показать. Гарантируется, что все \(a_i\) различны.

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

битмаски Разбор случаев

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

Подтасовка результатов#50550

В городе Н. олимпиада по информатике состоит из двух туров, каждый из которых оценивается из 400 баллов. Для удобства все её участники занумерованы числами от 1 до \(N\).

Сразу после проведения олимпиады курьер принёс жюри пренеприятнейшее известие: <<сверху>> пришло указание о том, что некто Вася, выступавший в олимпиаде под номером 1, должен занять как можно более высокое место, то есть как можно меньше участников должны набрать по сумме двух туров больше баллов, чем Вася. При этом места, занятые школьниками в каждом из туров в отдельности, уже опубликованы, и их менять нельзя. Для каждого тура дан список номеров участников в порядке занятого места — перестановка чисел от 1 до \(N\). Теперь работа жюри заключается в том, чтобы расставить целые баллы от 1 до 400 каждому участнику в первом и втором турах таким образом, чтобы в итоговой таблице Вася занял как можно более высокое место, а места участников в каждом из туров не изменились. При этом никакие два участника не должны получить в одном туре одинаковые баллы.

Ваша задача — проделать за жюри такую работу.

Считается, что участник по сумме двух туров занял место \(A\), если ровно \(A-1\) участников набрали по сумме двух туров строго больше баллов.

Формат входных данных
Сначала вводится целое число \(N\) (\(1 \le N \le 200\)) — количество участников олимпиады. Во второй строке перечислены номера участников в порядке занятых мест в первом туре (от первого места до \(N\)-го). В третьей строке в таком же формате следует описание второго тура. Номера участников во второй и третьей строках разделены пробелами.

Формат выходных данных
Сначала выведите \(N\) целых чисел от 1 до 400, соответствующих расстановке баллов участникам первого тура, где \(i\)-ое число — балл в первом туре участника, занявшего на нём \(i\)-е место, затем аналогично \(N\) целых чисел, соответствующих расстановке баллов во втором туре. Числа разделяйте пробелами или переводами строки. Никакие два участника не должны получить одинаковые баллы в одном и том же туре. Если существует несколько способов расставить баллы требуемым образом, выведите любой из них.

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

Задача на реализацию Разбор случаев

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

Помогаем природе#48932

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

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

Возле тропинки растут \(n\) деревьев, текущие уровни влажности которых заданы массивом \(a_1, a_2, \dots, a_n\). Леон научился трем способностям, которые помогут ему осушать и поливать почву.

Он может выбрать позицию \(i\) и уменьшить уровень влажности деревьев \(1, 2, \dots, i\) на \(1\).
Он может выбрать позицию \(i\) и уменьшить уровень влажности деревьев \(i, i + 1, \dots, n\) на \(1\).
Увеличить уровень влажности всех деревьев на \(1\).

Леон хочет узнать минимальное число действий, которое необходимо совершить, чтобы каждое дерево имело уровень влажности равный \(0\).

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(1 \leq n \leq 200\,000\)).

Во второй строке вводятся \(n\) целых чисел \(a_1, a_2 \ldots a_n\) (\(-10^9 \leq a_i \leq 10^9\)) — изначальные уровни влажности деревьев.

Формат выходных данных
Выведите одно целое число — минимальное число действий.

В первом примере из условия достаточно \(2\) раза применить операцию прибавления \(1\) ко всему массиву.

Во втором примере из условия можно \(4\) раза применить операцию вычитания на префиксе длины \(3\) и получить массив \(6, 0, 3\).

После этого \(6\) раз применить операцию вычитания на префиксе длины \(1\) и \(3\) раза операцию вычитания на суффиксе длины \(1\). Итого, количество действий составит \(4 + 6 + 3 = 13\). Можно показать, что меньшим количеством действий обойтись нельзя, поэтому \(13\) — это ответ.

Разбор случаев

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

Не летное положение#47204

Три скворца сидят на ветке дерева. Ветку дерева будем считать числовой прямой. С учетом этого, можно сказать, что скворцы сидят в трёх разных точках с целочисленными координатами a, b, c. Когда скорцам становится скучно, один из крайних скворцов перелетает на другое место (скворец считается крайним, если слева или справа нет другого скворца). Причем, из-за того, что скворцы не хотят улетать друг от друга слишком далеко, скворец, который решил сменить положение, перелетает только в целочисленную точку между двумя другими скворцами, если такая есть. Скворцы могут менять свое положение до тех пор пока их положение не станет "не летным". "Не летным" называется положение, при котором ни один из скорцов не может перелететь и сесть между двумя другими в целочисленную точку.

По начальному положению скворцов определите минимальное и максимальное число перелетов, которые могут совершить скворцы, пока не попадут в какое-нибудь "не летное" положение.

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

В трёх строках заданы три различных целых числа - a, b, c (1 <= a, b, c <= 10¹⁸), исходные позиции скворцов.

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

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

Примеры

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

Разбор случаев

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

Счастливчики#46948

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

Все деньги должны быть распределены.
Каждый должен получить как минимум 1 рубль.
Никто не должен получить 4 рубля (это совсем не счастливая сумма).

Определите максимальное количество Счастливчиков, если вы разделите деньги в соответствии с вышеупомянутыми правилами. Если нет способа разделить деньги, верните -1.

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

Ограничения

1 <= money <= 200
2 <= children <= 30

Выходные данные
Выведите максимальное количество Счастливчиков.

Примеры

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

Разбор случаев Условный оператор

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

Два массива#45674

Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i², у профессора Селезнева i-й член последовательности равен i³. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз.

Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности.

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

В единственной строке входного файла дано натуральное число i (1 <= i <= 10⁷).

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

Выведите i-е число новой последовательности.

Примеры

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

Вывод формулы Разбор случаев Сортировка слиянием

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

Лягушки#44504

Три лягушки сидят на числовой прямой в трёх различных точках с целочисленными координатами a, b, c. Лягушки боятся отступать слишком далеко друг от друга, поэтому прыгать может только одна из крайних лягушек (такая, что слева или справа от нее нет других лягушек) и только в целочисленную точку между двумя другими лягушками, если такая есть. Заметим, что в некоторых положениях ни одна из лягушек прыгнуть не может, назовем их стабильными .

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

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

В трёх строках заданы три различных целых числа - a, b, c (1 <= a, b, c <= 10¹⁸), исходные позиции лягушек.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

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

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

Примечание

В первом примере из условия лягушка с позиции 4 может прыгнуть на позицию 2 и образовать стабильное положение (1,2,3). Можно показать, что больше одного прыжка они сделать не смогут.

Во втором тесте из условия лягушка с позиции 1 может прыгнуть на позицию 4, а затем лягушка с позиции 10 может прыгнуть на позицию 3, тем самым придя в стабильное положение (2,3,4) за два прыжка. Можно показать, что больше 7 прыжков по описанным правилам лягушки сделать не могли.

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

В четвёртом тесте из условия лягушка с позиции 1 может прыгнуть на позицию 4, а затем лягушка с позиции 5 может прыгнуть на позицию 3, тем самым придя в положение (2,3,4) за два прыжка. Можно показать, что больше двух прыжков лягушки сделать не могли.

Примеры

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

Разбор случаев

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

Майки и носки#44310

Как известно, осенью и зимой светает поздно и так хочется утром ещё хоть немного поспать, а не идти в школу! Некоторые школьники готовы даже одеваться, не открывая глаз, лишь бы отложить момент пробуждения. Вот и Саша решил, что майку и носки он вполне может вытащить из шкафа на ощупь с закрытыми глазами и только потом включить свет и одеться.
В шкафу у Саши есть два ящика. В одном из них лежит A синих и B красных маек, в другом — C синих и D красных пар носков. Саша хочет, чтобы и майка, и носки были одного цвета. Он вслепую вытаскивает M маек и N пар носков. В первое же утро Саша задумался, какое минимальное суммарное количество предметов одежды (M + N) он должен вытащить, чтобы среди них гарантированно оказались майка и носки одного цвета. Какого именно цвета окажутся предметы одежды, для Саши совершенно неважно.

Входные данные
На вход программе подаются четыре целых неотрицательных числа A, B, C, D, записанных в отдельных строках: A — количество синих маек, B — количество красных маек, C — количество синих носков, D — количество красных носков. Все числа не превосходят 10⁹ . Гарантируется, что в шкафу есть одноцветный комплект из майки и носков.

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

Примеры

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

Замечание
В примере из условия в шкафу лежит A = 6 синих маек и B = 2 красных маек. Если взять 3 майки, то среди них обязательно найдётся синяя. В другом ящике лежит C = 7 пар синих носков и D = 3 пары красных носков. Если взять 4 пары, то среди них обязательно будет пара синих
носков. Поэтому если взять вслепую 3 майки и 4 пары носков, то среди них обязательно найдётся одноцветный (синий) комплект из майки и носков.

Задача на реализацию Разбор случаев

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

Подарки#42937

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

Входные данные
Первая строка входных данных содержит целое положительное число N — количество конфет в одном подарке. Вторая строка входных данных содержит целое неотрицательное число A — количество упаковок из одной конфеты. Третья строка содержит целое неотрицательное число B — количество упаковок из трёх конфет.
Чиcло N и общее число конфет на складе не превосходят 2 × 10⁹.

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

Примеры

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

Замечание
В примере из условия на складе имеются 8 упаковок из одной конфеты и 2 упаковки из трёх конфет. В один подарок необходимо положить 4 конфеты. Два подарка можно собрать, используя 1 упаковку из одной конфеты и 1 упаковку из трёх конфет. Ещё один подарок можно собрать из 4 упаковок из одной конфеты. Всего было использовано 6 упаковок из одной конфеты и 2 упаковки из трёх конфет, осталось 2 упаковки из одной конфеты, которых не хватит на дополнительный подарок.

Вывод формулы Разбор случаев

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

Лазерная пушка#38774

У игрока в космической стрелялке есть очень мощная лазерная пушка. Но она неподвижна и может стрелять только в одном направлении. Игрок может расставить на игровом поле двусторонние зеркала, меняющие ход луча, чтобы поражать врагов. Введём декартову систему координат с центром, где расположена пушка, то есть пушка имеет координаты (0; 0). Пушка стреляет в направлении точки (1; 1). Игрок может поставить зеркала в точках с целочисленными координатами. Зеркала могут быть горизонтальными или вертикальными, попадание луча в зеркало меняет траекторию луча по законам отражения света. Некоторые возможные варианты отражения луча от зеркала изображены на рисунке.

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

Входные данные
Программа получает на вход два целых числа X и Y , не превосходящих по модулю 10000, записанные в разных строках — координаты цели. Точка (X; Y) не совпадает с началом координат.

Выходные данные
Программа должна вывести в первой строке число N — необходимое количество зеркал. Следующие N строк должны содержать информацию о каждом зеркале. В i-й строке должны быть записаны через пробелы два целых числа xi и yi и один символ ti , обозначающие координаты (xi ; yi) точки, в которых установлено i-е зеркало, и тип этого зеркала ti . Если ti является символом «V», то i-е зеркало размещено вертикально, если же ti является символом «H», то зеркало размещено горизонтально. Например, строка «-2 5 H» обозначает горизонтальное зеркало в точке (−2; 5). Зеркала можно выводить в любом порядке. Зеркало нельзя размещать в точке (0; 0), также нельзя размещать два зеркала в одной точке. Значения xi и yi не должны по модулю превосходить 100 000. Также, разумеется, нельзя допустить, чтобы отражённый луч попал в пушку. Если вариантов ответа несколько, выведите любой из них. Если поразить цель в соответствии с условиями задачи невозможно, программа должна вывести одно число «-1». Если для поражения цели зеркала не нужны, программа должна вывести одно число «0»

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1	1 3 3 H

Задача на реализацию Разбор случаев Элементарная геометрия

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

Голосование#38749

Коротышки решили взять в полет на Луну либо Незнайку либо Пончика. Не сумев договориться, они решили проголосовать. Незнайка и Пончик наблюдают краткий отчет о голосовании. Коротышки показывают Незнайке и Пончику соотношение текущего количества голосов, полученных Незнайкой и Пончиком, но не фактическое количество голосов. Незнайка и Пончик посмотрели отчет N раз, и когда они смотрели его в i-й (1<=i<=N) раз, соотношение было P_i:N_i. Известно, что Незнайка и Пончик имели хотя бы один голос, когда впервые увидели отчет. Найдите минимально возможное общее количество голосов, полученных Незнайкой и Пончиком, когда они проверили отчет в N-й раз. Можно предположить, что количество голосов, полученных Незнайкой и Пончиком, никогда не уменьшается.

Входные данные
В первой строке задается целое число N (1<=N<=1000). В следующих N строках записано по 2 числа P_iи N_i(1<=P_i,N_i<=1000). P_iи N_i- взаимно простые числа.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 2 3 1 1 3 2	10	Количество голосов, полученных Пончиком и Незнайкой, изменяется так 2,3 → 3,3 → 6,4. Общее количество голосов в конце составляет 10, что является минимально возможным числом.
2	4 1 1 1 1 1 5 1 100	101	Возможно, что ни Пончик ни Незнайка не получили голосов между моментом, когда они смотрели отчет, и моментом, когда они смотрели его в следующий раз.
3	5 3 10 48 17 31 199 231 23 3 2	6930

Разбор случаев Циклы

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

Карты на троих#38491

Антонин, Бальбин и Цезарь играют в игру "Карты на троих", алгоритм которой следующий:
- сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт. На каждой карточке написана буква a, b или c. Порядок карт в колодах не может быть изменен;
- игроки ходят по очереди. Антонин ходит первым;
- если в колоде текущего игрока есть хотя бы одна карта, ему необходимо сбросить верхнюю карту в колоде;
- следующий ход переходит к игроку, имя которого начинается с буквы на сброшенной карте (a - Антонин, b - Бальбин, c - Цезарь);
- если колода текущего игрока пуста, игра заканчивается, и текущий игрок выигрывает игру.
Вам выдаются начальные колоды игроков (Sa, Sb, Sc). Состояние колоды Антонина записано в строке Sa, где i-й (\(1<=i<=len(S_a)\)) символ это буква в i-й карты в колоде. Строка Бальбина (Sb) и строка Цезаря (Sс) описываются таким же образом.
Определите победителя в игре.

Формат входных данных
На вход подаются три ненулевых строки Sa, Sb и Sc, каждая с новой строки. Длина каждой строки не более 100 символов. Каждая строка состоит только из букв a, b или c.

Формат выходных данных
Если выиграл Антонин. то выведите букву A, если Бальбин - букву B, если Цезарь - букву C.

Примечание
В первом тестовом примере игра будет развиваться следующим образом:
Антонин сбрасывает верхнюю карту своей колоды, a. Антонин делает следующий ход.
Антонин сбрасывает верхнюю карту своей колоды, с. Цезарь следующий.
Цезарь сбрасывает верхнюю карту своей колоды, с. Цезарь следующий.
Цезарь сбрасывает верхнюю карту своей колоды: a. Антонин делает следующий ход.
Антонин сбрасывает верхнюю карту своей колоды: a. Антонин делает следующий ход.
Колода Антонина пуста. Игра заканчивается, и Антонин выигрывает игру.

Простые игры Разбор случаев

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

Квест#38479

Новый квест, в котором участники должны выбраться с территории проведения, представляет собой прямоугольник из N × M комнат. Каждая комната имеет четыре двери, ведущие в соседние комнаты, из комнат на краю прямоугольника двери ведут наружу, через эти двери можно
покинуть территорию проведения квеста.
В начале квеста в каждой комнате находится по человеку, а все двери заперты. После начала квеста организаторы дистанционно открывают в каждой комнате запирающий механизм одной из четырёх дверей. Теперь человек, находящийся в этой комнате, может открыть эту дверь и перейти
в соседнюю комнату, через другие три двери выйти из этой комнаты нельзя. При этом может оказаться так, что дверь, соединяющая две комнаты, будет отпираться только с одной стороны, тогда пройти через эту дверь можно только с той стороны, с которой она будет открываться, проходить
через дверь в обратном направлении нельзя, если в соседней комнате будет отперта не эта дверь, а какая-то другая. Если комната находится на краю территории и из этой комнаты открыта дверь наружу, то, пройдя через эту дверь, участник навсегда покидает территорию квеста.
После начала квеста и отпирания дверей участники начинают перемещаться между комнатами. Каждый участник перемещается в соседнюю открытую комнату и продолжает перемещаться до тех пор, пока не покинет территорию квеста. Однако возможна ситуация, когда некоторые участники будут бесконечно перемещаться между комнатами и никогда не выйдут наружу.
Разработчики квеста попросили Вас составить такой план отпирания дверей, при котором ровно K человек смогут выбраться наружу с территории квеста.
Входные данные
Программа получает на вход три числа N, M, K, 1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ K ≤ NM. N и M – количество строк и столбцов в прямоугольном плане квеста, K – количество человек, которые должны выйти из квеста.
Выходные данные
Программа должна вывести план территории квеста в виде N строк, каждая из которых должна содержать M символов. Символ соответствует тому, какая дверь будет открыта в данной комнате и может быть одной из следующих заглавных английских букв: U (дверь в верхнюю по данному плану комнату), D (дверь в нижнюю комнату), L (дверь в левую комнату), R (дверь в правую комнату). Необходимо вывести один любой подходящий план решения задачи. Если ни одного подходящего плана не существует, программа должна вывести одну строчку «IMPOSSIBLE».».

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 2 1	IMPOSSIBLE	Территория квеста состоит из 1 строки и 2 столбцов. При любом способе открытия дверей из квеста не сможет выбраться ровно один человек.
2	3 4 5	RDLD ULUR DURU	Территория квеста состоит из 3 строк и 4 столбцов. Из квеста должны выйти 5 человек. На рисунке ниже приведена картинка, соответствующая ответу из примера. Стрелками обозначены открытые двери, точками помечены комнаты, обитатели которых выйдут из квеста.

Задача на реализацию Конструктив Разбор случаев

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

Перевернутые родословные#38385

Учёный Иван Иванович изучает перевёрнутые родословные. Перевёрнутая родословная представляет собой набор людей, про каждого из которых известны либо оба его родителя, либо не известен ни один родитель. Кроме того, известно, что у всех людей из родословной есть ровно один
ребёнок, кроме одного человека, у которого детей вовсе нет. Поэтому, если пронумеровать людей целыми числами от 1 до n, то можно обозначить за s_i номер ребёнка человека с номером i и сказать, что s_i = 0 в случае, если у человека с номером i детей нет.
Будем считать, что человек a входит в родословную человека b, если либо a = b, либо если у b известны родители, и a входит в родословную одного из родителей b.

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

Формат входных данных
В единственной строке заданы два целых числа n и k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — количество людей в родословной и количество перекосов в ней.

Формат выходных данных
В первой строке выведите «YES» (без кавычек), если существует родословная с n людьми и k перекосами, и «NO» (без кавычек) в противном случае.
Если требуемая родословная существует, то во второй строке выведите n целых чисел s1, s2, . . . , sn (0 ≤ s_i ≤ n), задающих номера детей каждого из n человек в родословной. Если искомых родословных несколько, выведите любую.

Примеры

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

Замечание

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

Во втором примере подойдет следующая родословная:

В этом случае в родословную человека 1 входят пять человек (люди 1, 2, 3, 4, 5), в родословную человека 2 входит один человек (только 2), в родословную человека 3 входят три человека (3, 4, 5), в родословную человека 4 входит один человек (только 4) и в родословную человека 5 входит один
человек (только 5). В этом случае происходит перекос родословной в человеке 1.
В третьем примере можно показать, что не существует родословной из трёх людей с двумя перекосами.

Вывод формулы Задача на реализацию Разбор случаев

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

Проверка автомата#38299

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

Автомат представляет собой последовательность из блоков двух типов: максимизаторов и минимизаторов . На каждом блоке написано некоторое натуральное число x . Максимизатор принимает на вход натуральное число a и подает на выход число max ( x , a ) . Минимизатор принимает на вход натуральное число a и подает на выход число min ( x , a ) .

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

Изначально в автомате нет ни одного блока, и он просто возвращает число, которое принимает.

Андрюша последовательно выполняет действия с автоматом. Действия бывают трех типов:

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

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

Входные данные
Первая строка входных данных содержит единственное целое число n ( 1 ≤ n ≤ 4·10⁵ ) — суммарное количество действий Андрюши.

В каждой из следующих n строк содержится по два целых числа t и x ( 1 ≤ t ≤ 3 , 1 ≤ x ≤ 10⁹ ), где t — это тип очередного действия. Если t = 1 , то Андрюша хочет добавить к автомату максимизатор, на котором написано число x . Если t = 2 , то Андрюша хочет добавить к автомату минимизатор, на котором написано число x . Если t = 3 , то Андрюша хочет подать на вход автомату число x и узнать, что получится на выходе.

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

Примеры

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

Разбор случаев

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

Выбор конфет#38292

Скоро у Гарри Поттера день рождения! Гермиона хочет приготовить для него необычный подарок. Она хочет подарить Гарри набор из n волшебных конфет. Каждая конфета характеризуется её вкусом — целым числом t_i . Удовольствие , которое получит Гарри от набора конфет — это сумма вкусов всех конфет в этом наборе. Обратите внимание, что вкусы конфет, как и удовольствие Гарри, не обязательно должны быть положительными.

У Гермионы есть огромная коробка с конфетами, в которой для каждого целого числа t от - 10⁹ до 10⁹ лежит ровно одна конфета со вкусом t . Гермиона хочет взять из этой коробки n конфет, из которых будет состоять набор для Гарри.

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

Входные данные
Первая строка входных данных содержит единственное целое число n ( 1 ≤ n ≤ 100 ) — количество конфет, которое хочет Гермиона положить в набор. Вторая строка входных данных содержит единственное целое число s ( - 10⁹ ≤ s ≤ 10⁹ ) — удовольствие, которое должен получить Гарри от набора.

Выходные данные
Если составить желаемый набор из имеющихся у Гермионы конфет невозможно, выведите « NO ». Иначе, в первой строке выведите « YES », а во второй строке в произвольном порядке n чисел — вкусы конфет в искомом наборе. Если правильных ответов несколько, выведите любой из них.

Примеры

№	Входные данные	Выходные данные
1	3 10	YES 500000000 -500000000 10

Одномерные массивы Разбор случаев

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

Нью-Кэпитал#38273

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

Улицы в новой столице образуют правильную прямоугольную сетку, в которой все улицы пересекаются ровно через одну местную единицу длины. Вертикально идущие улицы называются улицами, а горизонтально идущие — аллеями. Всего в городе получилось 2000 улиц и 2000 аллей, поэтому, чтобы не придумывать много новых названий, их все просто пронумеровали. Улицы пронумеровали с запада на восток числами от −1000 до 999, а аллеи — с юга на север, тоже числами от −1000 до 999. Центром города считаются кварталы на пересечении улиц и аллей с номерами от −100 до 100.

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

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

Входные данные
В первой строке даны два числа x1 и y1 — номер улицы и номер аллеи, на пересечении которых находится мэрия. В второй строке даны два числа x2 и y2 — номер улицы и номер аллеи, на пересечении которых находится дом мэра. Все числа целые и не превосходят по модулю 100.

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

Примеры

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

Обход в ширину Разбор случаев

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