Ёжик решил сходить на командную олимпиаду. Оказалось, что дом ёжика находится в точке $$$0$$$, а олимпиада проходит в точке $$$x$$$ $$$(x \gt 0)$$$ координатной прямой. За один шаг ёжик может переместиться на $$$1, 2, 3, 4, 5, 6$$$ или $$$7$$$ позиций вперёд. Помогите ему определить, за какое минимальное количество шагов он может добраться до олимпиады.
В первой строке входных данных записано одно целое число $$$x$$$ ($$$1 \le x \le 1 000 000$$$) — координата места проведения олимпиады.
Выведите минимальное количество шагов, которые необходимо сделать ёжику, чтобы попасть из точки $$$0$$$ в точку $$$x$$$.
7
1
16
3
Нужно упаковать ровно $$$n$$$ сувениров. Есть коробки двух типов: коробка первого типа вмещает $$$a$$$ сувениров, а коробка второго типа — $$$b$$$ сувениров. Коробок каждого типа неограниченное количество.
Каждая использованная коробка должна быть полностью заполнена. Найдите минимальное общее количество коробок и укажите, сколько коробок каждого типа нужно взять. Допустимо использовать коробки только одного типа.
В трёх строках входных данных записаны три целых числа $$$n$$$, $$$a$$$ и $$$b$$$ ($$$1 \le n, a, b \le 10^6$$$) — количество сувениров и вместимости коробок первого и второго типов соответственно.
Если упаковать ровно $$$n$$$ сувениров невозможно, выведите единственное целое число $$$-1$$$.
Иначе в первой строке выведите целое число $$$k$$$ — минимальное общее количество коробок. Во второй строке выведите два неотрицательных целых числа $$$x$$$ и $$$y$$$ — количество коробок первого и второго типов соответственно. Должны выполняться равенства $$$ax + by = n$$$ и $$$x + y = k$$$.
Если оптимальных вариантов несколько, выведите любой из них.
1646
3 1 2
746
-1
933
3 0 3
В первом примере можно взять одну коробку первого типа и две коробки второго типа: $$$1 \cdot 4 + 2 \cdot 6 = 16$$$. Двух коробок недостаточно.
Во втором примере вместимость каждой коробки чётна, поэтому упаковать ровно $$$7$$$ сувениров невозможно.
В третьем примере типы коробок имеют одинаковую вместимость. Подойдёт любое распределение трёх коробок между типами.
Пётр — известный прыгун, который каждый день улучшает технику своих прыжков. Если сегодня Пётр прыгнул на $$$x$$$ метров, то завтра он прыгнет на $$$x + d$$$ метров ($$$1 \le d$$$). Параметр $$$d$$$ (улучшения) для всех дней одинаковый. Пётр уже провёл $$$n$$$ тренировок и записал длины всех прыжков в дневник. Ему интересно, на сколько он сможет прыгнуть завтра, но записи в его дневнике перемешались. Помогите Петру узнать дальность прыжка на следующий день после последней тренировки, записанной в дневник.
В первой строке ввода дано единственное целое число $$$n$$$ ($$$2 \le n \le 1000$$$) — количество записей в дневнике Петра.
В следующих $$$n$$$ строках записано по одному натуральному числу, не превосходящему $$$10^9$$$, — перемешанные результаты тренировок.
Гарантируется, что записи корректные, соответствуют описанному увеличению прыжков.
В единственной строке вывода напишите целое число — длина прыжка Петра после тренировок.
31269
15
Согласно представленным записям, в первый день прыжок составлял 6 метров, во второй 9, а в третий день 12, значит в четвёртый день Петя прыгнет на 15 метров.
В научной лаборатории решили провести важный эксперимент. Для его проведения была сделана специальная конструкция. Она состоит из двух рядов, второй ряд расположен прямо под первым, в каждом из рядов находится $$$n$$$ лампочек. К сожалению, на складе не нашлось необходимого количества работающих лампочек, поэтому некоторые из лампочек — перегоревшие.
Однажды ночью кто-то пробрался в лабораторию, выкрутил все лампочки, находящиеся во втором ряду, перемешал их и в случайном порядке вкрутил обратно во второй ряд. Причём рабочие лампочки остались рабочими, а перегоревшие — перегоревшими (даже если они оказались на новой позиции). Порядок лампочек был очень важен для проведения эксперимента, поэтому необходимо вернуть всё как было.
К несчастью, никто не помнит, в каком порядке находились лампочки второго ряда, однако один из стажёров лаборатории перед происшествием успел записать массив $$$c$$$, где $$$c_i$$$ означает, что в $$$i$$$–м столбце работало $$$c_i$$$ лампочек. Помогите восстановить исходный порядок лампочек во втором ряду — для каждой из $$$n$$$ лампочек второго ряда выведите, работала она или нет. Если стажёр ошибся и не существует такого порядка лампочек, выведите «NO».
Первая строка входных данных содержит целое число $$$n$$$ — количество лампочек в каждом ряду $$$(1 \le n \le 2 \cdot 10^5)$$$.
Вторая строка входных данных содержит $$$n$$$ целых чисел — информацию о лампочках первого ряда. $$$i$$$–е число равно 0, если $$$i$$$–я лампочка не работала, и 1 — иначе.
Третья строка входных данных содержит $$$n$$$ целых чисел — информацию о лампочках второго ряда после происшествия в формате, аналогичном первому ряду.
Четвёртая строка входных данных содержит $$$n$$$ чисел — массив $$$c$$$ $$$(0 \le c_i \le 2)$$$, $$$i$$$–е число равно количеству работающих лампочек в $$$i$$$–м столбце до происшествия.
Если подходящий порядок лампочек существует, выведите на первой строке «YES», а на второй строке — подходящее расположение лампочек, где $$$i$$$–е число равно 1, если лампочка работает, и 0 — иначе. Количество работающих лампочек в выведенном втором ряду должно совпадать с количеством работающих лампочек во втором ряду после происшествия.
Если возникшая ситуация невозможна, в единственной строке выведите «NO».
«YES» и «NO» можно выводить в любом регистре (верхнем или нижнем).
61 1 0 1 0 10 0 1 1 1 12 2 1 1 1 1
YES 1 1 1 0 1 0
41 1 1 11 1 0 12 2 2 2
NO
Петя нашёл странный игральный аппарат. Он вводит в него натуральное число $$$n$$$, после чего аппарат начинает последовательно изменять это число.
За один ход аппарат делает следующую операцию:
- Перемножает все цифры текущего числа $$$n$$$ и вычитает из полученного произведения $$$1$$$. Полученное число становится новым текущим числом.
- Если полученное число не является натуральным, то Петя проигрывает и игра заканчивается.
- Если полученное число является простым, Петя выигрывает и игра заканчивается.
- Иначе, аппарат переходит к следующему ходу.
В первой строке требуется вывести итог игры: строку «WIN» или «LOSE» (без кавычек) в случае выигрыша или проигрыша Пети соответственно. Во второй строке требуется вывести номер хода, на котором закончилась игра.
Например, пусть $$$n = 25$$$. После первого хода $$$n = 2 * 5 - 1 = 9$$$. После второго хода: $$$n = 9 - 1 = 8$$$. После третьего: $$$n = 8 - 1 = 7$$$. 7 — простое число, поэтому Петя выигрывает на 3 ходу. Если $$$n = 10$$$, то после первого хода: $$$n = 1 * 0 - 1 = -1$$$ — не натуральное, поэтому Петя проиграет на $$$1$$$ ходу.
Простым числом является натуральное число, которое имеет ровно 2 различных натуральных делителя: $$$1$$$ и само себя.
В единственной строке дано натуральное число $$$n$$$ ($$$1 \le n \le 10^6$$$).
В первой строке выведите итог игры — строку «WIN» или «LOSE» (без кавычек). Во второй строке выведите единственное число — номер хода, на котором закончилась игра.
25
WIN 3
10
LOSE 1
16767
WIN 5
Это лёгкая версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.
На доске записано $$$n$$$ неотрицательных чисел $$$a_1,a_2,\ldots,a_n$$$.
Петя читает числа слева направо и складывает их. После $$$a_n$$$ он снова переходит к $$$a_1$$$, затем к $$$a_2$$$ и так далее. То есть одна и та же последовательность из $$$n$$$ чисел повторяется сколько угодно раз.
Найдите минимальное количество прочитанных чисел, после которого их сумма станет не меньше $$$S$$$.
Если это невозможно, выведите $$$-1$$$.
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 100$$$). Во второй строке дано целое число $$$S$$$ ($$$1 \le S \le 1000$$$).
В следующих $$$n$$$ строках записано по одному числу $$$a_i$$$ ($$$0 \le a_i \le 100$$$).
Выведите минимальное целое число $$$k$$$, для которого сумма первых $$$k$$$ элементов бесконечной последовательности не меньше $$$S$$$.
Если набрать сумму $$$S$$$ невозможно, выведите $$$-1$$$.
37123
4
В примере бесконечная последовательность имеет вид $$$1, 2, 3, 1, 2, 3, \ldots$$$. Сумма первых трёх элементов равна $$$6$$$, а сумма первых четырёх — $$$7$$$, поэтому ответ равен $$$4$$$.
Это сложная версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.
На доске записано $$$n$$$ неотрицательных чисел $$$a_1,a_2,\ldots,a_n$$$.
Петя читает числа слева направо и складывает их. После $$$a_n$$$ он снова переходит к $$$a_1$$$, затем к $$$a_2$$$ и так далее. То есть одна и та же последовательность из $$$n$$$ чисел повторяется сколько угодно раз.
Найдите минимальное количество прочитанных чисел, после которого их сумма станет не меньше $$$S$$$.
Если это невозможно, выведите $$$-1$$$.
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 10^5$$$). Во второй строке дано целое число $$$S$$$ ($$$1 \le S \le 10^{12}$$$).
В следующих $$$n$$$ строках записано по одному числу $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$).
Выведите минимальное целое число $$$k$$$, для которого сумма первых $$$k$$$ элементов бесконечной последовательности не меньше $$$S$$$.
Если набрать сумму $$$S$$$ невозможно, выведите $$$-1$$$.
37123
4
В примере бесконечная последовательность имеет вид $$$1, 2, 3, 1, 2, 3, \ldots$$$. Сумма первых трёх элементов равна $$$6$$$, а сумма первых четырёх — $$$7$$$, поэтому ответ равен $$$4$$$.
Это лёгкая версия задачи про дома. Сложная версия находится дальше, и входные данные в ней больше, из-за чего часть решений "лёгкой" версии может не сработать.
Вы любите дома и решили попробовать изобразить их в виде прямоугольных таблиц, состоящих из символов '+' и '#'. Знак '+' символизирует стену дома, а знак '#' — его окно. Чтобы дом выглядел реалистично, никакие символы-окна не должны находиться на краю таблицы или соприкасаться с другими символами-окнами по углу или стороне. Например, следующие дома не являются реалистичными:
| +++ | ++++ | +++++ |
| +#+ | ++#+ | +#+#+ |
| +++ | +#++ | +#+#+ |
| +#+ | ++++ | +++++ |
А эти дома являются реалистичными:
| +++ | ++++ | +++++ |
| +#+ | ++++ | +#+#+ |
| +++ | ++++ | +++++ |
| +#+ | ++++ | ++#++ |
| +++ | ++++ | +++++ |
Напишите программу, которая по заданным числам $$$n, m, k$$$ выводит любую возможную таблицу из $$$n$$$ строк и $$$m$$$ столбцов, изображающую реалистичный дом с $$$k$$$ окнами, либо определяет, что таких таблиц не существует.
В единственной строке вводятся три целых числа $$$n, m, k$$$ ($$$1 \le n, m \le 30$$$, $$$0 \le k \le 10$$$).
Выведите таблицу из $$$n$$$ строк и $$$m$$$ столбцов, изображающую реалистичный дом с $$$k$$$ окнами, если такая существует. Все символы в каждой строке таблицы должны выводиться слитно. Если существует несколько подходящих таблиц, вы можете вывести любую из них.
Если таких таблиц нет, выведите строку «impossible» строчными латинскими буквами и без кавычек.
5 5 3
+++++ ++#++ +++++ +#+#+ +++++
3 4 0
++++ ++++ ++++
Это сложная версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.
Вы любите дома и решили попробовать изобразить их в виде прямоугольных таблиц, состоящих из символов '+' и '#'. Знак '+' символизирует стену дома, а знак '#' — его окно. Чтобы дом выглядел реалистично, никакие символы-окна не должны находиться на краю таблицы или соприкасаться с другими символами-окнами по углу или стороне. Например, следующие дома не являются реалистичными:
| +++ | ++++ | +++++ |
| +#+ | ++#+ | +#+#+ |
| +++ | +#++ | +#+#+ |
| +#+ | ++++ | +++++ |
А эти дома являются реалистичными:
| +++ | ++++ | +++++ |
| +#+ | ++++ | +#+#+ |
| +++ | ++++ | +++++ |
| +#+ | ++++ | ++#++ |
| +++ | ++++ | +++++ |
Напишите программу, которая по заданным числам $$$n, m, k$$$ выводит любую возможную таблицу из $$$n$$$ строк и $$$m$$$ столбцов, изображающую реалистичный дом с $$$k$$$ окнами, либо определяет, что таких таблиц не существует.
В единственной строке вводятся три целых числа $$$n, m, k$$$ ($$$1 \le n,m \le 10^5$$$, $$$1 \le n \cdot m \le 10^5$$$, $$$0 \le k \le 10^9$$$).
Выведите таблицу из $$$n$$$ строк и $$$m$$$ столбцов, изображающую реалистичный дом с $$$k$$$ окнами, если такая существует. Все символы в каждой строке таблицы должны выводиться слитно. Если существует несколько подходящих таблиц, вы можете вывести любую из них.
Если таких таблиц нет, выведите строку «impossible» строчными латинскими буквами и без кавычек.
5 5 3
+++++ ++#++ +++++ +#+#+ +++++
3 4 0
++++ ++++ ++++
3 3 1000
impossible
Это лёгкая версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.
В один прекрасный день в Азероте открылась новая таверна. Сразу после открытия в ней нет ни одного посетителя, но постепенно туда начали заходить герои, искатели приключений и просто подозрительные личности.
За вечер последовательно происходят $$$n$$$ событий трёх типов:
- 'A' — в таверну заходит общительный посетитель и сразу знакомится со всеми, кто уже находится внутри;
- 'B' — в таверну заходит молчаливый посетитель и ни с кем не знакомится;
- 'C' — кто-то разыгрывает заклинание 'Mass Hysteria' на всех, кто в этот момент находится в таверне. После него каждые два знакомых посетителя забывают друг друга, а каждые два незнакомых — внезапно знакомятся.
Знакомство взаимно: если первый посетитель знаком со вторым, то и второй знаком с первым. Посетитель не считается знакомым с самим собой.
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 50$$$) — количество событий.
Во второй строке дана строка $$$s$$$ длины $$$n$$$, состоящая из символов 'A', 'B' и 'C'. Символ $$$s_i$$$ задаёт тип $$$i$$$-го события.
Выведите $$$n$$$ целых чисел. $$$i$$$-е число должно быть равно количеству посетителей с нечётным числом знакомых сразу после $$$i$$$-го события.
5AABCB
0 2 2 2 2
7ABACCCA
0 0 2 2 2 2 2
Это сложная версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.
В один прекрасный день в Азероте открылась новая таверна. Сразу после открытия в ней нет ни одного посетителя, но постепенно туда начали заходить герои, искатели приключений и просто подозрительные личности.
За вечер последовательно происходят $$$n$$$ событий трёх типов:
- 'A' — в таверну заходит общительный посетитель и сразу знакомится со всеми, кто уже находится внутри;
- 'B' — в таверну заходит молчаливый посетитель и ни с кем не знакомится;
- 'C' — кто-то разыгрывает заклинание 'Mass Hysteria' на всех, кто в этот момент находится в таверне. После него каждые два знакомых посетителя забывают друг друга, а каждые два незнакомых — внезапно знакомятся.
Знакомство взаимно: если первый посетитель знаком со вторым, то и второй знаком с первым. Посетитель не считается знакомым с самим собой.
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — количество событий.
Во второй строке дана строка $$$s$$$ длины $$$n$$$, состоящая из символов 'A', 'B' и 'C'. Символ $$$s_i$$$ задаёт тип $$$i$$$-го события.
Выведите $$$n$$$ целых чисел. $$$i$$$-е число должно быть равно количеству посетителей с нечётным числом знакомых сразу после $$$i$$$-го события.
5AABCB
0 2 2 2 2
7ABACCCA
0 0 2 2 2 2 2
Это лёгкая версия задачи про плакаты. Сложная версия находится дальше, и входные данные в ней больше, из-за чего часть решений "лёгкой" версии может не сработать.
Электронный плакат представляет собой прямоугольную таблицу символов. Изначально он состоит из $$$h$$$ строк и $$$w$$$ столбцов. Затем контроллер последовательно выполняет $$$q$$$ команд.
Команда задаётся двумя целыми числами $$$a$$$, $$$b$$$ и строчной латинской буквой $$$c$$$. Пусть непосредственно перед командой плакат имел $$$h$$$ строк и $$$w$$$ столбцов. После команды его размеры становятся равны
$$$$$$ \max(h,a) \times \max(w,b). $$$$$$
Все существовавшие до команды клетки сохраняют свои символы. Каждая клетка, которой до команды не существовало, заполняется буквой $$$c$$$. В частности, если одновременно появились и новые строки, и новые столбцы, клетки на их пересечении тоже заполняются буквой $$$c$$$.
Если оба указанных размера не превосходят текущие размеры плаката, команда ничего не изменяет.
Выведите плакат после выполнения всех команд.
В первой строке даны три целых числа $$$h$$$, $$$w$$$ и $$$q$$$ ($$$1 \le h, w \le 100$$$, $$$1 \le q \le 100$$$) — начальное количество строк, начальное количество столбцов и количество команд.
В следующих $$$h$$$ строках записано по $$$w$$$ строчных латинских букв — начальное содержимое плаката.
В следующих $$$q$$$ строках даны два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le 100$$$) и строчная латинская буква $$$c_i$$$ — описание очередной команды.
Команды выполняются в том порядке, в котором они записаны во входных данных.
Выведите итоговое содержимое плаката: по одной строке для каждой строки таблицы.
1 1 3a1 3 x3 2 y2 5 z
axxzz yyyzz yyyzz
2 2 4abcd1 1 x3 4 p2 3 z4 4 q
abpp cdpp pppp qqqq
Это сложная версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.
Электронный плакат представляет собой прямоугольную таблицу символов. Изначально он состоит из $$$h$$$ строк и $$$w$$$ столбцов. Затем контроллер последовательно выполняет $$$q$$$ команд.
Команда задаётся двумя целыми числами $$$a$$$, $$$b$$$ и строчной латинской буквой $$$c$$$. Пусть непосредственно перед командой плакат имел $$$h$$$ строк и $$$w$$$ столбцов. После команды его размеры становятся равны
$$$$$$ \max(h,a) \times \max(w,b). $$$$$$
Все существовавшие до команды клетки сохраняют свои символы. Каждая клетка, которой до команды не существовало, заполняется буквой $$$c$$$. В частности, если одновременно появились и новые строки, и новые столбцы, клетки на их пересечении тоже заполняются буквой $$$c$$$.
Если оба указанных размера не превосходят текущие размеры плаката, команда ничего не изменяет.
Выведите плакат после выполнения всех команд.
В первой строке даны три целых числа $$$h$$$, $$$w$$$ и $$$q$$$ ($$$1 \le h, w \le 1000$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — начальное количество строк, начальное количество столбцов и количество команд.
В следующих $$$h$$$ строках записано по $$$w$$$ строчных латинских букв — начальное содержимое плаката.
В следующих $$$q$$$ строках даны два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le 2 \cdot 10^5$$$) и строчная латинская буква $$$c_i$$$ — описание очередной команды.
Команды выполняются в том порядке, в котором они записаны во входных данных.
Гарантируется, что в любой момент $$$h \cdot w \le 10^6$$$, в том числе после всех операций, когда плакат самый большой.
Выведите итоговое содержимое плаката: по одной строке для каждой строки таблицы.
1 1 3a1 3 x3 2 y2 5 z
axxzz yyyzz yyyzz
2 2 4abcd1 1 x3 4 p2 3 z4 4 q
abpp cdpp pppp qqqq
Это лёгкая версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.
Дан массив из $$$n$$$ натуральных чисел $$$a_1, a_2, \ldots, a_n$$$.
Разрешается изменить значения некоторых элементов массива. После изменений все элементы также должны оставаться натуральными числами.
Требуется получить массив, сумма элементов которого равна $$$S$$$, изменив минимально возможное количество элементов исходного массива.
Если это возможно, выведите любой подходящий массив с минимальным количеством изменённых элементов. Если получить сумму $$$S$$$ невозможно, выведите $$$-1$$$.
В первой строке записаны два целых числа $$$n$$$ и $$$S$$$ ($$$1 \le n \le 1000$$$, $$$1 \le S \le 10^9$$$).
Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
Если решения не существует, выведите $$$-1$$$.
Иначе выведите $$$n$$$ натуральных чисел — изменённый массив. Его сумма должна быть равна $$$S$$$, а количество позиций, в которых он отличается от исходного массива, должно быть минимально возможным.
5 14 3 4 5 2 8
3 2 5 2 2
В примере изначально сумма чисел в массиве равна $$$22 = 3 + 4 + 5 + 2 + 8$$$, изменив второй и пятый элемент добились суммы $$$14 = 3 + 2 + 5 + 2 + 2$$$. Заметим, что изменением одного элемента нельзя было обойтись, ибо числа должны остаться натуральными.
Это сложная версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.
Дан массив из $$$n$$$ натуральных чисел $$$a_1, a_2, \ldots, a_n$$$.
Разрешается изменить значения некоторых элементов массива. После изменений все элементы также должны оставаться натуральными числами.
Требуется получить массив, сумма элементов которого равна $$$S$$$, изменив минимально возможное количество элементов исходного массива.
Если это возможно, выведите любой подходящий массив с минимальным количеством изменённых элементов. Если получить сумму $$$S$$$ невозможно, выведите $$$-1$$$.
В первой строке записаны два целых числа $$$n$$$ и $$$S$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le S \le 10^9$$$).
Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
Если решения не существует, выведите $$$-1$$$.
Иначе выведите $$$n$$$ натуральных чисел — изменённый массив. Его сумма должна быть равна $$$S$$$, а количество позиций, в которых он отличается от исходного массива, должно быть минимально возможным.
5 14 3 4 5 2 8
3 2 5 2 2
В примере изначально сумма чисел в массиве равна $$$22 = 3 + 4 + 5 + 2 + 8$$$, изменив второй и пятый элемент добились суммы $$$14 = 3 + 2 + 5 + 2 + 2$$$. Заметим, что изменением одного элемента нельзя было обойтись, ибо числа должны остаться натуральными.
Красный и синий роботы находятся в разных целочисленных точках плоскости. У каждого робота есть пульт с записанной последовательностью из $$$n$$$ команд.
Каждая команда перемещает робота на одну клетку:
- U увеличивает координату $$$y$$$ на $$$1$$$;
- D уменьшает координату $$$y$$$ на $$$1$$$;
- L уменьшает координату $$$x$$$ на $$$1$$$;
- R увеличивает координату $$$x$$$ на $$$1$$$.
Изначально красный робот держит первый пульт, а синий - второй.
В секунду $$$i$$$ оба робота одновременно выполняют команду номер $$$i$$$ со своего текущего пульта. После того как оба переместились, проверяются их позиции. Если роботы оказались в одной точке, они обмениваются пультами.
Во время движения по единичному отрезку обмена быть не может. В частности, если роботы одновременно прошли навстречу друг другу и поменялись местами, но после команды оказались в разных точках, это не считается встречей.
После обмена нумерация команд продолжается: в следующую секунду каждый робот выполняет команду номер $$$i+1$$$ со своего нового пульта.
Обратите внимание, при некоторых входных данных обмен пультами может происходить после каждого перемещения. Это не противоречит условию задачи.
Определите конечные позиции красного и синего роботов после выполнения всех $$$n$$$ команд.
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$).
Во второй строке даны четыре целых числа $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ — начальные координаты красного и синего роботов соответственно. Каждая координата находится в диапазоне от $$$-10^9$$$ до $$$10^9$$$. Начальные позиции роботов различны.
В третьей строке дана строка $$$s_1$$$ длины $$$n$$$ — команды первого пульта.
В четвёртой строке дана строка $$$s_2$$$ длины $$$n$$$ — команды второго пульта.
Обе строки состоят только из символов U, D, L и R.
В первой строке выведите конечные координаты красного робота.
Во второй строке выведите конечные координаты синего робота.
30 0 2 0RRULLU
0 1 2 1
30 0 2 0RUULUR
1 2 2 1
20 0 1 0RULD
1 1 0 -1
В первом примере после первой секунды оба робота оказываются в точке $$$(1,0)$$$ и обмениваются пультами. Во вторую секунду красный робот выполняет команду L со второго пульта, а синий - команду R с первого. В третью секунду оба выполняют команду U.
Во втором примере роботы встречаются после первой и после второй секунды. Они дважды обмениваются пультами, поэтому третью команду каждый выполняет со своего исходного пульта.
В третьем примере после первой секунды роботы меняются позициями. Это не считается встречей, поэтому пульты остаются у прежних владельцев.
Это лёгкая версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.
На научной станции исследуют температурные условия. Известны $$$2n$$$ различных целых значений температуры $$$x_1 \lt x_2 \lt \ldots \lt x_{2n}$$$.
Они задают $$$n$$$ непересекающихся диапазонов: $$$[x_1,x_2]$$$, $$$[x_3,x_4]$$$, ..., $$$[x_{2n-1},x_{2n}]$$$. Исследователя интересуют все целые температуры, попавшие хотя бы в один из этих диапазонов. Найдите их среднее арифметическое.
Целое число $$$x$$$ принадлежит диапазону $$$[l,r]$$$, если $$$l\le x\le r$$$.
В первой строке дано натуральное число $$$n$$$ ($$$1 \le n \le 100$$$).
В следующих $$$2n$$$ строках записано по одному целому числу $$$x_i$$$ ($$$0 \le x_i \le 1000$$$). Гарантируется, что $$$x_1 \lt x_2 \lt \ldots \lt x_{2n}$$$.
Выведите среднее арифметическое всех целых температур из заданных диапазонов. Абсолютная погрешность ответа не должна превышать $$$10^{-6}$$$.
2 1 3 5 8
4.571428
3 1 5 7 10 995 1000
402.26666666
В первом примере рассматриваются отрезки $$$[1, 3]$$$ и $$$[5, 8]$$$. Целые числа, входящие хотя бы в один из них: $$$1, 2, 3, 5, 6, 7, 8$$$. Их среднее арифметическое: $$$\frac{1 + 2 + 3 + 5 + 6 + 7 + 8}{7} = \frac{32}{7} \approx 4.57142857$$$. Тогда верными ответами будут считаться: $$$4.571428$$$; $$$4.5714284$$$; $$$4.571429$$$, а неверными: $$$4.571427$$$; $$$4.5714273$$$.
Это сложная версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.
На научной станции исследуют температурные условия. Известны $$$2n$$$ различных целых значений температуры $$$x_1 \lt x_2 \lt \ldots \lt x_{2n}$$$.
Они задают $$$n$$$ непересекающихся диапазонов: $$$[x_1,x_2]$$$, $$$[x_3,x_4]$$$, ..., $$$[x_{2n-1},x_{2n}]$$$. Исследователя интересуют все целые температуры, попавшие хотя бы в один из этих диапазонов. Найдите их среднее арифметическое.
Целое число $$$x$$$ принадлежит диапазону $$$[l,r]$$$, если $$$l\le x\le r$$$.
В первой строке находится единственное натуральное число n ($$$1 \le n \le 10^5$$$). В следующих $$$2n$$$ строках записано по одному целому числу: $$$x_1, x_2, \ldots, x_{2n}$$$ ($$$|x_i| \le 10^9$$$ для всех $$$1 \le i \le 2n$$$).
Выведите единственное число — среднее арифметическое целочисленных точек отрезков с абсолютной погрешностью не более $$$10^{-6}$$$.
2-3-125
1.1428571428571427937
3-156-25-2789981003
-13.082191780821917249
В первом примере рассматриваются отрезки [$$$-3, -1$$$] и [$$$2, 5$$$]. Целые числа, входящие хотя бы в один из них: $$$-3, -2, -1, 2, 3, 4, 5$$$. Их среднее арифметическое: $$$\frac{-3 - 2 - 1 + 2 + 3 + 4 + 5}{7} = \frac{8}{7} \approx 1.14285714$$$. Тогда верными ответами будут считаться: $$$1.142857$$$; $$$1.1428571$$$; $$$1.142858$$$, а неверными: $$$1.142856$$$; $$$1.1428561$$$.