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

50096#50096

Требуется разделить заданный текст на английском языке на 3 группы слов по их первой букве так, чтобы количество слов в группах отличалось на минимальную величину. Группы могут формироваться только на основе алфавитного порядка латинских букв и задаются в виде диапазонов, например a-i, j-o, p-z.

Входные данные
В первой строке записано число N, не превышающее 10⁶ - количество строк в тексте. Далее записано N строк текста, в каждой из которых не более 1000 символов. Текст состоит из латинских букв разного регистра, пробелов и знаков препинания ".", ",", "!", "?", ":".
После каждого знака препинания обязательно ставится пробел либо строка заканчивается.
Переносы слов с одной строки на другую отсутствуют.

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	3 Above all zoo the blue bird soars. Hippopotamus hopes high honey hotel?	2	Слова можно разбить на 3 группы: 1-я - 4 слова на буквы a и b; 2-я - 5 слов на букву h; 3-я - 3 слова на буквы s-z.
2	2 A a a a, o. O o o! A?	5	Слова можно разбить на 2 группы: 1-я - все слова на букву a; 2-я - все слова на букву o; 3-я - пустая.

Строки

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

50095#50095

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	8.4	1	8.4₁₀=13.2₅, количество разрядов целой части на 1 больше, чем дробной
2	1.5	7	1.5₁₀=1.(2)₅=1.22222222₅, в 5-й с/с дробь не имеет конечного представления, поэтому ограничиваем длину 8 дробными разрядами

Вещественные числа Разные системы счисления

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

Угадай число#49316

Август и Беатриса играют в игру. Август загадал натуральное число от 1 до n. Беатриса пытается угадать это число, для этого она называет некоторые множества натуральных чисел. Август отвечает Беатрисе YES, если среди названных ей чисел есть задуманное или NO в противном случае. После нескольких заданных вопросов Беатриса запуталась в том, какие вопросы она задавала и какие ответы получила и просит вас помочь ей определить, какие числа мог задумать Август.

Формат входных данных

Первая строка входных данных содержит число n — наибольшее число, которое мог загадать Август. Далее идут строки, содержащие вопросы Беатрисы. Каждая строка представляет собой набор чисел, разделенных пробелами. После каждой строки с вопросом идет ответ Августа: YES или NO.

Наконец, последняя строка входных данных содержит одно слово HELP.

Формат выходных данных

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

Множества

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

Облако хештегов#49295

Вася ведёт публичную страницу организации “Мышь и клавиатура”, где постоянно публикует различные новости из мира спортивного программирования. Для удобства поиска по новостям Вася прикрепляет к каждой из них список хештегов. В данной задаче хештегом называется строка, состоящая из маленьких букв английского алфавита и ровно одного символа ‘#’, расположенного в начале строки. Длиной хештега будем называть количество символов в нём, без учёта символа ‘#’.

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

Поскольку вам не хочется менять порядок хештегов в уже написанной новости, вы решили удалить у некоторых хештегов некоторый суффикс (какое-то количество последних символов), при этом можно даже удалить весь текст хештега, оставив только символ ‘#’, но сам символ ‘#’ удалять нельзя. Из всех возможных вариантов такого удаления вы хотите выбрать тот, в котором суммарно будет удалено минимальное количество символов. Если и таких вариантов несколько, то разрешается использовать любой из них.

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

Каждая из следующих \(n\) строк содержит ровно один хештег положительной длины.

Обозначим через \(L\) суммарную длину всех хештегов. Гарантируется, \(L\) не превосходит \(500\,000\).

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

Замечание

Слово \(a_1, a_2, \ldots, a_m\) длины \(m\) лексикографически меньше слова \(b_1, b_2, \ldots, b_k\) длины \(k\), если выполняется одно из двух:

либо в первой позиции \(i\), такой что \(a_i \neq b_i\), символ \(a_i\) идёт раньше по алфавиту, чем символ \(b_i\), то есть в первой различающейся позиции символ слова \(a\) меньше символа слова \(b\);
либо (если такой позиции нет) \(m < k\), то есть второе слово начинается с первого, но при этом не совпадает с ним.

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

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

Слово, состоящее только из символа ‘#’, лексикографически меньше любого другого хештега. Поэтому в третьем примере мы не можем оставить два первых слова и сократить два вторых.

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 35 тестах будут доступны во время соревнования. Результаты работы на остальных 15 будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq n, L \leq 15\), наберут не менее \(20\) баллов.

Решения, корректно работающие при \(1 \leq n, L \leq 1\,000\), наберут не менее \(50\) баллов.

Решения, корректно работающие при \(1 \leq n, L \leq 100\,000\), наберут не менее \(70\) баллов.

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

✓ 2✗ 4—Войти и решать

Игра с таблицей#48967

Дана таблица \(A\) из \(h\) строк и \(w\) столбцов, в каждой ячейке которой записано целое число. Строки пронумерованы от \(1\) до \(h\) сверху вниз, столбцы пронумерованы от \(1\) до \(w\) слева направо.

Разрешается применять к этой таблице следующие операции:

выбрать столбец таблицы и удалить его (столбцы слева и справа от него становятся соседними);
выбрать строку таблицы и удалить ее (строки сверху и снизу от нее становятся соседними).

Эти операции разрешается применить произвольное число раз в любом порядке.

Определите, возможно ли при помощи этих операций получить из исходной таблицу с суммой чисел, равной заданному числу \(s\), и если да, то какие операции и в каком порядке необходимо применить.

Формат входных данных

Первая строка ввода содержит числа \(h\) и \(w\) — размеры таблицы (\(1 \leq h, w \leq 15\)).

Каждая из следующих \(h\) строк содержит по \(w\) целых чисел — таблицу \(A\) (\(0 \leq A_{i,j} \leq 10^{9}\)).

В последней строке ввода находится число \(s\) — необходимая сумма (\(1 \leq s \leq 10^{18}\)).

Формат выходных данных
Если получить таблицу с суммой чисел \(s\) из исходной невозможно, выведите строку <<NO>>.

Иначе:

В первой строке выведите строку <<YES>>.
Во второй строке выведите единственное число \(k\) — количество операций с таблицей, которые необходимо применить, чтобы получить из неё таблицу с суммой чисел \(s\).
В каждой из следующих \(k\) строк выведите по два целых числа \(t_{j}, i_{j}\), где \(t_{j} = 1\), если очередная операция производится со строкой, и \(t_{j}=2\), если она производится со столбцом таблицы. Число \(i_{j}\) должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с которой эта операция производится.

В первом примере изначально дана следующая таблица:

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array}\)

Удалив третьи строку и столбец получим таблицу с суммой чисел \(8\):

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|} \hline 1 & 2 \\ \hline 2 & 3 \\ \hline \end{array}\)

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

В третьем примере изначально дана таблица:

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array}\)

Удалив последние две строки и первый столбец, получим таблицу с суммой чисел \(34\):

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|} \hline 2 & 1 & 4 & 5 \\ \hline 5 & 4 & 1 & 2 \\ \hline 2 & 4 & 3 & 1 \\ \hline \end{array}\)

meet in the middle Битовые операции

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

Анаграммы#48946

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

Формат входных данных

Даны два слова на отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.

Формат выходных данных

Требуется вывести "YES" – если введенные слова являются анаграммами друг друга, "NO" – если нет.

Алгоритмы обработки Строки

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

Вордл наоборот#48935

Камила и Динара играют в <<Wordle>>. Камила загадала слово длины \(n\), состоящее из различных латинских букв. Динара сделала одну попытку угадать и назвала слово длины \(n\), также состоящее из различных латинских букв. Камила раскрасила буквы в догадке Динары в соответствии со следующими правилами:

Буква, совпадающая с буквой в загаданном слове, красится в зеленый цвет и обозначается G.
Буква, которая присутствует в загаданном слове, но стоит не своей позиции, красится в жёлтый цвет и обозначается Y.
Буква, отсутствующая в загаданном слове, красится в белый цвет и обозначается W.

Например, если было загадано слово ALERT, а догадка была ALONE, то буквы будут раскрашены в цвета GGWWY. Первые две буквы в словах совпадают, поэтому они зеленые. Буква E есть в загаданном слове, но находится на другой позиции, поэтому она жёлтая. Остальные буквы белые, так как их нет в загаданном слове.

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

В первой строке вводится одно целое число \(n\) \((1 \le n \le 10)\) — длина загаданного слова.

Во второй строке вводится строка длины \(n\), состоящая из заглавных латинских букв — загаданное слово. Гарантируется, что все буквы в нем различны.

В третьей строке вводится строка длины \(n\), состоящая из букв G, Y, W — цвета, в которые были раскрашены буквы в слове Динары.

Если подходящих слов не существует, выведите No.

Если хотя бы одно подходящее слово существует, в первой строке выведите Yes, во второй — любое подходящее слово.

Разберем первый пример из условия.

Буквы H и G не встречаются в загаданном слове, поэтому они белые.

Буквы E и B встречаются, но на других позициях, поэтому они жёлтые

Буквы C и D совпадают с буквами на соответствующих позициях в загаданном слове, поэтому они зелёные.

Есть и другие ответы, любой правильный ответ будет зачтен.

Обратите внимание, что строка HECDBH не является ответом, так как в ней есть совпадающие буквы.

Задача на реализацию Перебор Строки

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

Палиндромные числа#48933

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

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

Число называется палиндромом, если оно читается одинаково справа налево и слева направо. Например, числа \(121, 66, 98989\) являются палиндромами, а \(103, 239, 1241\) — нет.

После некоторых размышлений Алина поняла, что такое число всегда можно найти. Помогите Алине найти подходящее число!

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

Во второй строке вводится одно положительное целое число длины \(n\). Гарантируется, что оно не содержит ведущих нулей.

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

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

В первом примере из условия \(99 + 32 = 131\) — палиндром. Число \(12\) также будет являться ответом, так как \(99 + 12 = 111\).

Во втором примере из условия \(1023 + 8646 = 9669\).

В третьем примере из условия \(385 + 604 = 989\).

Задача на реализацию Строки

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

Строка Громозеки#48050

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

Формат входных данных
Первые две строки входных данных содержат строки S и T, соответственно. Длины строк больше 0 и меньше 50000, строки содержат только строчные латинские буквы.

Формат выходных данных
Выведите в порядке возрастания индексы символов, начиная с которых строка T входит в строку S (в одной строке должно быть записано одно число).

Строки

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

Телефонный справочник#48046

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

Формат входных данных
В единственной строке содержится одно слово, состоящее из строчных латинских букв от "a" до "z" (2 ≤ n ≤ 10⁶)

Формат выходных данных
Выведите одно слово - новое название компании. Если название не~изменилось, выведите изначальное название.

Задача на реализацию Линейный поиск Строки

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

Гласная подстрока#48030

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

Формат входных данных
Программа получает на вход строку s (10 <= s <= 10⁶). Строка состоит из символов английского алфавита, записанных в верхнем регистре (от A до Z). Гласные буквы английского алфавита: AEIOUY.

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

Поиск подстроки в строке Строки

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

Самая длинная подстрока#48025

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

Формат входных данных
Программа получает на вход строку s (10 <= s <= 10⁶). Строка состоит из символов английского алфавита, записанных в верхнем регистре (от A до Z).

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

ЕГЭ_информатика Поиск подстроки в строке Строки

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

Шнурки#47969

Обувная фабрика собирается начать выпуск элитной модели ботинок. Дырочки для шнуровки будут расположены в два ряда, расстояние между рядами равно a, а расстояние между дырочками в ряду b. Количество дырочек в каждом ряду равно N. Шнуровка должна происходить элитным способом “наверх, по горизонтали в другой ряд, наверх, по горизонтали и т.д.” (см. рисунок). Кроме того, чтобы шнурки можно было завязать элитным бантиком, длина свободного конца шнурка должна быть l. Какова должна быть длина шнурка для этих ботинок?
Запрещено использовать операторы if, while, for, repeat-until (Паскаль)

Входные данные: Программа получает на вход четыре натуральных числа a, b, l и N.

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

Примеры
входные данные
2
1
3
4
выходные данные
26

Вывод формулы Целые числа

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

Артефакты Максимуса#47741

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

Входные данные
Программа получает на вход три строки s1, s2, s3 - последовательности символов, записанные на каждом из артефактов.

Constraints:

1 <= |s1|, |s2|, |s3| <= 100

s1, s2 и s3 состоят только из строчных английских букв

|s| означает длину последовательности s

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

Строки

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

Сломанный автомат#47709

Громозека является одним из ведущих в Галактике космических археологов. Возвращаясь домой с очередной археологической экспедиции, он решил привезти своим четырем детям их любимые печенья. Ему осталось только вбить необходимое количество килограмм на экране терминала, и автомат сразу выдаст ему печенье . Но, вот незадача, на терминале сломались все кнопки с цифрами и буквами. Работают только цифры 0 и 1. Громозека в задумчивости, как же ему заказать ровно n килограмм. Он придумал, что может сделать несколько заказов таким образом, чтобы каждый заказ мог состоять только из цифр 0 и 1. Вот только Громозека очень торопится, потому что до старта корабля осталось совсем немного времени. Помогите Громозеке определить минимальное число раз, которым ему придется воспользоваться автоматом, чтобы купить ровно n килограмм и порадовать своих детей!

Например, чтобы купить 12 киллограмм печенья Громозека может воспользоваться автоматом дважды, купив сначала 11 килограмм печенья, затем - 1 килограмм.

Входные данные
Программа получает на вход целое число n (1 <= n <= 10⁹).

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

Примеры

№	Входные данные	Выходные данные
1	1234	4

Целые числа Циклы

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

Паровозики на числовой прямой#47637

Паровозики стоят на железной дороге параллельно друг другу на параллельных участках пути. Условно весь участок железной дороги можно представить в виде числовой прямой. В этом случае i-й паровозик на данной числовой прямой покрывает некоторое количество заданных целых точек (от точки start_i до точки end_i, включая данные точки).

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

Входные данные
В первой строке записано число N - количество паровозиков на железной дороге. В следующих N строках записаны по 2 числа (start_i, end_i) - тоски начала и конца i-го паровозика.

Ограничения

1 <= N <= 100 1 <= start_i <= end_i <= 100

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

Примеры

№	Входные данные	Выходные данные	Примечания
1	3 3 6 1 5 4 7	7	Все точки от 1 до 7 покрыты хотя бы одним паровозиком. Поэтому ответ 7.

Множества

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

Внутреннее представление целого числа в шестнадцатеричном формате#47351

Для заданного целого числа со знаком num найдите его внутренее представление в памяти компьютера в шестнадцатеричной системе счисления (в 32-разрядной сетке).

Входные данные
Программа получает на вход целое число num (-2³¹ <= num <= 2³¹ - 1).

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

Примеры

№	Входные данные	Выходные данные
1	26	1a
2	-1	ffffffff

Битовые операции

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

Расстояние Хэмминга между двумя числами#47349

Расстояние Хэмминга между двумя целыми числами - это количество позиций, в которых соответствующие биты различаются.
Для заданных двух целых чисел x и y, найдите расстояние Хэмминга между ними.

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

Ограничения

0 <= x, y <= 2³¹ - 1

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	1 4	2	1 (0 0 0 1) 4 (0 1 0 0)

Битовые операции

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

Василий собирает ягоды#47308

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

Входные данные
Программа получает на вход два целых числа N и K (N > 0, 0 ≤ K ≤ N, K<=10⁹, N<=2*10⁹), записанные в отдельных строках, — текущее количество ягод в корзинке медведя Василия и количество ягод малины в корзинке.

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	27 7	3	В примере всего ягод в корзинке 27, из которых малины 7 ягод. Если в собрать ещё 3 ягоды малины, то в корзинке станет 30 ягод, из которых малины будет 10.

Бинарный поиск по ответу Вывод формулы Целые числа

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

Декодируй массив#47285

Магистр Максимус создал массив из n неотрицательных целых чисел, но чтобы сохранить его в тайне, он преобразовал его в другой массив encoded длиной n-1. Каждый элемент encoded_i был получен путем выполнения операции XOR над двумя соседними элементами arr[i] и arr[i+1]. Например, если исходный массив arr = [1,0,2,1], то полученный массив encoded = [1,2,3].

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

Помогите Магистру Максимусу восстановить исходный массив arr! Мы уверены, что ответ существует и является уникальным. Расшифруйте тайну и восстановите массив arr.

Входные данные
Программа получает на вход в первой строке число n - количество элементов исходного массива. Вторая строка содержит n-1 число encoded_i - элементы закодированного массива.

Ограничения

2 <= n <= 10⁴
Длина массива encoded == n - 1
0 <= encoded_i <= 10⁵
0 <= first <= 10⁵

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

Примеры

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

Битовые операции

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