В финал соревнования по удою «Большой удой» прошли Архип и Бронислав. В течение раунда каждый надоил ведро молока (возможно, неполное), после чего результаты были записаны на листочек, а вёдра с молоком были одновременно опрокинуты в большой чан. Отметка в чане показала, что суммарно было надоено $$$L$$$ литров молока. Но только участники отвлеклись на вручение призов, как листочек с результатами съела коза.
Баба Надя, недавно приобрёвшая слуховой аппарат, заявила что может восстановить результаты на слух. По вековому опыту она знает, что молоко из ведра льется со скоростью 1 литр в секунду. А на слух она определила, что во время финала молоко лилось в течение $$$T$$$ секунд. Помогите ответить на вопрос — на сколько литров победитель обогнал проигравшего?
В первой строке дано целое число $$$L$$$ – количество литров молока, надоенного финалистами ($$$1 \le L \le 10^9$$$).
Во второй строке дано целое число $$$T$$$ – время, в течение которого лилось молоко ($$$1 \le T \le 10^9$$$, $$$T \le L \lt 2 \cdot T$$$).
Выведите единственное целое число – разницу между количеством молока в литрах, надоенного финалистами.
3 2
1
6 4
2
42 24
6
На направлении ФИИТ в Уральском Федеральном Университете учат не только математике и программированию, но и решению необычных задач. Предлагаем вам решить одну такую задачу:
Есть популярный вид головоломок, в которых нужно вставить арифметические операции в число, чтобы получить другое число. Вам дана одна строка:
Вы можете вставить в неё скобки и знаки арифметических выражений +, -, *, /. Ваша цель — получить ровно $$$100$$$. Придумайте решение и сообщите нам ваше выражение, и, может быть, вам поставят за это $$$100$$$ баллов!
В этой задаче ровно один тест. Для вашего удобства во входных данных даётся единственная строка «$$$12340$$$» (без кавычек). Считывать её необязательно.
Выведите единственную строку без пробелов — математическое выражение, требуемое в условии. Оно должно состоять из цифр $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$0$$$ в таком порядке; операций +, -, *, / (коды 43, 45, 42, 47 соответственно); и круглых скобок (коды 40, 41). Выражение должно быть математически корректным: скобки должны быть сбалансированы, и операции должны стоять строго между операндами, кроме ведущего минуса в начале выражения или после открывающей скобки. Разрешено ставить несколько цифр рядом, чтобы образовать многозначное число. При выполнении всех операций, выражение должно давать $$$100$$$.
Длина ответа должна не превосходить $$$30$$$ символов.
12340
(1+23)*(4+0)
Обратите внимание, что ответ в примере неверен и приведён только для иллюстрации формата. В нём арифметическое выражение соответствует формату, но результат равен $$$96$$$, а не $$$100$$$.
Вадим недавно оказался в офисе Яндекса и первым делом он пошёл к вендомату к чипсами. У него есть с собой небольшая сумма денег, но проблема в том, что это только однорублёвые и однокопеечные монеты, причём копеек у него меньше ста. Вадим сильно хочет есть, поэтому готов купить самую дорогую пачку чипсов в вендомате, но он не хочет получать сдачи. Помогите Вадиму найти такую пачку, либо ответить, что такой нет.
В первой строке даны два числа $$$N$$$ и $$$M$$$ — количество пачек чипсов в вендомате и сумма денег у Вадима $$$(1 \le N \le 10^5)$$$. Число $$$M$$$ имеет вид «$$$R,cc$$$», где $$$R$$$ — количество рублей в сумме денег без ведущих нулей $$$(0 \le R \le 999)$$$, а $$$cc$$$ — количество копеек в сумме денег $$$(00 \le cc \le 99)$$$.
В следующих $$$N$$$ строках описаны пачки чипсов названием $$$s_i$$$ и стоимостью $$$c_i$$$. Числа $$$c_i$$$ имеют такой же вид, как и $$$M$$$.
Гарантируется, что названия пачек чипсов не повторяются, содержат в себе только прописные и строчные латинские символы, а также имеют длину не больше $$$10$$$.
Выведите название подходящей для Вадима пачки чипсов, если она существует, либо «$$$-1$$$» в обратном случае. Если существует несколько оптимальных ответов, выведите любой из них.
3 89,54 ChipsIT 69,69 YaChips 99,09 noChips 0,00
noChips
...все разговаривают на иворильском языке. Его очень легко понять — в нём только существительные и глаголы, которые могут сочетаться между собой в любой комбинации. Существительные представляют из себя последовательность чередующихся между собой гласных и согласных букв, а глаголы — последовательность гласных букв. Любая такая последовательность является словом. А используют иворильцы только строчные латинские буквы. Гласными в иворильском являются буквы '$$$a$$$', '$$$e$$$', '$$$i$$$', '$$$o$$$', '$$$u$$$' и '$$$y$$$', остальные буквы — согласные.
Молодая Кугона пошла стажироваться в популярную иворильскую газету «Namenu iou», но она оказалась очень разочарована тем, что ей дали работу, которой никто больше не хотел заниматься — проверять готовый текст на орфографические ошибки. Гордая иворилка не хочет заниматься этой работой, а если и придётся, она хочет сократить потраченное время, исправив как можно меньше символов на правильные. Окажите помощь Кугоне в написании программы для автоматизации проверки текста, она будет очень благодарна Вам.
В первой строке дано одно целое число $$$N$$$ — количество слов в тексте $$$(1 \le N \le 10^5)$$$.
Во второй строке даны $$$N$$$ слов этого текста $$$s_i$$$ через пробел $$$(1 \le |s_i| \le 10^6)$$$.
Гарантируется, что суммарная длина слов не превосходит $$$10^6$$$.
Выведите единственное целое число — минимальное количество орфографических ошибок в тексте.
3 augaa feeer evtry
3
4 naumen is the best
4
Группа компаний СКБ Контур давно работает над революционным проектом, который будет помогать всем предпринимателям: от маленьких бизнесов до больших фирм. Они ещё не готовы раскрыть его суть, но на недавней пресс-конференции сообщили, что сейчас проект имеет номер версии $$$N$$$.
По слухам вы знаете, что в СКБ Контур есть необычная конвенция наименования версий. Каждый месяц они работают над новой версией. Номер первой версии выбирается произвольно из всех натуральных чисел. А каждый следующей месяц номер увеличивается на $$$1$$$ в каждом разряде. То есть, если номер текущей версии состоит из $$$k$$$ цифр, то в следующем месяце номер версии будет на $$$111 \ldots 111$$$ больше, где $$$1$$$ повторено $$$k$$$ раз.
Например, если сейчас СКБ Контур работает над версией номер $$$13579$$$, то через меcяц будут работать над версией $$$24690$$$.
Узнав, что номер текущей версии — $$$N$$$, вы тут же заинтересовались: какое наибольшее число месяцев могла идти работа над проектом? Попробуйте найти этот ответ.
В единственной строке дано натуральное число $$$N$$$ — текущий номер версии ($$$1 \le N \le 10^{18}$$$).
Выведите единственное натуральное число — наибольшее число месяцев, которое могла идти работа (считая текущий).
100
9
9
9
1
1
В первом примере компания могла начать с версии номер $$$12$$$, и восемь месяцев спустя номер версии будет равен $$$100$$$. Тогда у них идёт девятый месяц работы.
В некоторой стране есть $$$N$$$ городов, расположенных на одной прямой. В каждом городе находится по $$$s_i$$$ достопримечательностей.
Чтобы туристы могли любоваться не только достопримечательностями одного города, компания X-tensive решила установить в каждом городе по телескопу. Однако никто не хочет, чтобы туристы могли видеть больше $$$R$$$ достопримечательностей из одного города, иначе они не захотят посещать другие города. Для этого можно отрегулировать силу у каждого телескопа. Сила «$$$0$$$» означает, что туристы могут наблюдать только достопримечательности города, где находится этот телескоп, сила «$$$1$$$» — туристы могут увидеть достопримечательности ещё и соседних городов, сила «$$$2$$$» — вдобавок идут соседи этих соседей и так далее. Конечно же, сила телескопа в городе не должна быть настолько большой, чтобы обзор выходил за пределы страны в обоих направлениях.
После долгих обсуждений компания X-tensive приняла решение поставить максимальную возможную силу у каждого телескопа, но так, чтобы она удовлетворяла всем требованиям. Ответьте, какую силу нужно установить для каждого телескопа, либо «$$$-1$$$», если это невозможно.
В первой строке вводятся через пробел два целых числа $$$N$$$ и $$$R$$$ — количество городов в стране и ограничение на количество видимых достопримечательностей из одного города $$$(3 \le N \le 10^5$$$, $$$1 \le R \le 10^{14})$$$.
В следующей строке вводится $$$N$$$ целых чисел $$$s_i$$$ через пробел — количество достопримечательностей в каждом из городов в порядке их расположения на прямой $$$(1 \le s_i \le 10^9)$$$.
Выведите $$$N$$$ строк. В $$$i$$$-й строке выведите силу телескопа в $$$i$$$-м городе, удовлетворяющую всем условиям, либо «$$$-1$$$», если это невозможно.
3 3 1 2 1
1 0 1
3 4 1 2 1
2 1 2
3 4 1 3 5
1 0 -1
Сапёр — это игра на клетчатом поле, цель которой — найти расположение всех мин. Изначально все клетки поля скрыты. Нажатие на клетку её открывает, и если там находится мина — игрок тут же проигрывает. Если же в клетке нет мины, то в ней показывается число — суммарное количество мин в соседних клетках. Соседними считаются восемь смежных клеток по диагонали.
Игра Сапёр — не тривиальная, и часто в ней невозможно выиграть наверняка. Давайте рассмотрим упрощённую версию: одномерный Сапёр. Она играется на поле с всего двумя строчками, размера $$$2 \times N$$$. В первой строки расположены мины, а вторая строка пустая. Таким образом, каждая клетка второй строки всегда может быть открыта, и в ней записано число от $$$0$$$ до $$$3$$$ — количество мин в трёх соседних клетках первой строки (двух в случае крайних клеток).
Вот пример поля одномерного Сапёра ширины $$$6$$$:
Проблема в том, что даже в одномерном Сапёре решение не всегда можно гарантированно найти. Мы предлагаем вам для каждого $$$N$$$ посчитать количество возможный полей ширины $$$N$$$, которые можно гарантированно решить, не полагаясь на удачу.
В единственной строке дано одно целое число $$$N$$$ — ширина поля ($$$1 \le N \le 10^5$$$).
Выведите единственное число — количество различных полей размера $$$2 \times N$$$, которые можно гарантированно решить, по модулю $$$10^9 + 7$$$. Иными словами, если $$$x$$$ — количество таких полей, выведите $$$x \mod 10^9 + 7$$$. Два поля считаются различными, если мины в них расположены не на одних и тех же местах.
1
2
2
2
Во втором примере есть два поля, которые можно гарантированно решить:
Есть два других поля ширины $$$2$$$, но их невозможно отличить друг от друга просто посмотрев на нижний ряд:
Только что закончился матч века по игре в валуны. Его результат уже транслировали все каналы мира. Но уже скоро начнётся матч тысячелетия, и к нему надо подготовиться.
Как известно, в этой игре используется $$$N$$$ куч валунов, каждая из которых должна быть в определённом заранее отношении со всеми остальными. Причём, не важно, сколько именно валунов в каждой куче, при подготовке нужно просто соблюдать заданную пропорцию. Только нельзя оставлять все кучи пустыми!
К сожалению, предыдущие игроки не убрались за собой, а эту работу поручили делать Вадиму. Он может за одну минуту убрать один валун из одной кучи, а также прикатить один валун к любой куче тоже за минуту. Это неимоверно трудозатратная и времязатратная работа, поэтому это необходимо сделать как можно быстрее. Помогите Вадиму определить наименьшее время подготовки к матчу тысячелетия.
В первой строке дано целое число $$$N$$$ — количество куч валунов в игре $$$(2 \le N \le 10^5)$$$.
Во второй строке даны $$$N$$$ целых чисел $$$s_i$$$ — количество валунов в каждой из куч, оставшихся после матча века $$$(1 \le s_i \le 10^9)$$$.
В третьей строке даны $$$N$$$ целых чисел $$$p_i$$$ — необходимая для начала игры пропорция валунов в каждой из куч $$$(1 \le p_i \le 10^9)$$$.
Выведите одно целое число — наименьшее время для подготовки куч к матчу тысячелетия.
2 21 34 2 3
2
В примере Вадиму нужно подкатить валун к первой куче, затем убрать один валун из второй кучи. Тогда в кучах будет соответственно $$$22$$$ и $$$33$$$ валуна, что удовлетворяет пропорции $$$2:3$$$.
Вадим — большой фанат кусочно-линейных функций. Они имеют свои ограничения, и не любую функцию можно представить как кусочно-линейную. Вадим вам с радостью расскажет, что это такое.
Функция называется кусочно-линейной, если её график можно представить ломаной из $$$N$$$ вершин. А именно, она задаётся $$$n$$$ парами чисел $$$(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)$$$, которые являются координатами вершин ломаной. Обязательно должно выполняться условие $$$$$$x_1 \lt x_2 \lt x_3 \lt \ldots \lt x_N.$$$$$$
Этот набор точек задаёт функцию от одного аргумента, значение которой в $$$x_i$$$ равно $$$y_i$$$, а на промежутках между этими точками она линейная. Область определения такой функции — это отрезок $$$[x_1, x_N]$$$.
Валя придумал свой класс функций с одной переменной, которые он назвал модульными. Модульная функция состоит из $$$N$$$ слагаемых, каждое из которых имеет один из двух видов: $$$|a_i \cdot x + b_i|$$$ или $$$-|a_i \cdot x + b_i|$$$. Здесь $$$x$$$ — переменная, а $$$a_i$$$ и $$$b_i$$$ — параметры функции, а $$$| \ldots |$$$ обозначает взятие по модулю. Таким образом, модульная функция с $$$N$$$ слагаемыми имеет вид $$$$$$\pm|a_1 x + b_1| \pm |a_2 x + b_2| \pm \ldots \pm |a_N x + b_N|.$$$$$$
Вадим захотел проверить, не хуже ли модульные функции его любимых кусочно-линейных. Он принёс кусочно-линейную функцию с $$$N$$$ вершинами. Постарайтесь теперь найти модульную функцию с ровно $$$N$$$ слагаемыми, которая будет тождественно равна данной кусочно-линейной на отрезке $$$[x_1, x_N]$$$.
В первой строке дано целое число $$$N$$$ — количество вершин ломаной $$$(2 \le N \le 10^5)$$$.
Далее идёт $$$n$$$ строк, в каждой из которых через пробел даны два целых числа $$$x_i$$$, $$$y_i$$$ — координаты очередной вершины ($$$-10^5 \le x_i, y_i \le 10^5$$$).
Гарантируется, что координаты $$$x_i$$$ идут строго по возрастанию, то есть $$$$$$x_1 \lt x_2 \lt x_3 \lt \ldots \lt x_N.$$$$$$
Выведите в единственной строке модульную функцию из ровно $$$N$$$ слагаемых, тождественно равную данной кусочно-линейной функции на отрезке $$$[x_1, x_N]$$$. Придерживайтесь формата, показанного в примерах.
Функция должна состоять из $$$N$$$ слагаемых $$$|a_i x + b_i|$$$, разделённых знаками + и - (коды 43 и 45). Разрешается перед первым слагаемым поставить ведущий минус. Каждое слагаемое должно быть взято по модулю двумя символами | (код 124). Внутри слагаемого должен быть знак + (или -, если $$$b_i$$$ отрицательно). Левый операнд состоит из вещественного числа $$$a_i$$$ и переменной $$$x$$$ (код 120); знак умножения между ними не нужно писать, он подразумевается. Опускать $$$a_i$$$ или $$$b_i$$$ нельзя, даже если $$$a_i = 1$$$ или $$$b_i = 0$$$; нельзя также опускать левый операнд, если $$$a_i = 0$$$.
Таких слагаемых должно быть ровно $$$N$$$. Разрешено использовать слагаемые, тождественно равные нулю. Они могут быть записаны как |0x+0|.
Размер выходного файла должен быть не больше $$$8$$$ МБ. Ответ считается правильным, если в любой точке отрезка $$$[x_1, x_N]$$$ значение вашей модульной функции отличается от значения данной кусочно-линейной не более, чем на $$$0.01$$$.
2 1 0 2 1
-|0x-1|+|1x+0|
2 0 1 1 2
|1x-0|+|0x+1|
3 -1 1 0 -1 1 0
|-0.5x+1|-|0x-2|+|-1.5x-0|
Иллюстрация к третьему примеру:
В память о моём деде.
Мой дед — опытный лесник, он знает каждую полянку (их всего $$$N$$$ штук в лесу), каждую тропинку между определёнными двумя полянками, по которой можно ходить только в одну сторону (а тропинок $$$M$$$ штук), а также сколько на каждой тропинке растёт грибов и ягод в любой день.
Мой дед — человек привычки, и, как он рассказывал, привык он ходить в лес каждый день, начиная с полянки под номером $$$1$$$ и заканчивая на полянке под номером $$$N$$$. Естественно, что тропинки в лесу устроены так, что, проходя последовательно по ним, никогда не заблудишься, то есть не попадёшь на полянку, на которой уже был.
Мой дед ходил в лес в каждый из $$$Q$$$ дней лета, а в это время года на каждой полянке находится по рынку, где можно продавать грибы и ягоды. В $$$i$$$-й день на любой полянке можно продать грибы за $$$a_i$$$ рублей за штуку, а также ягоды за $$$b_i$$$ рублей за штуку. Мой дед же рассказывал, что каждый день, проходя каждую тропинку, он сразу же продавал все собранные на ней грибы и ягоды на соответствующем рынке по текущему курсу, причём на грибах он всегда зарабатывал больше, чем на ягодах.
Мой дед — любитель преувеличить свои достижения, поэтому мне нужна Ваша помощь. Определите для каждого из дней, правда ли, что мой дед смог пройти от $$$1$$$-й полянки до $$$N$$$-й и заработать на грибах больше, чем на ягодах, после прохождения каждой из тропинок. Заметьте, что в разные дни мой дед мог выбирать различный маршрут.
В первой строке даны три целых числа $$$N$$$, $$$M$$$ и $$$Q$$$ — количество полянок и тропинок в лесу и количество дней лета $$$(2 \le N \le 10^5, 1 \le M,Q \le 10^5)$$$.
В следующих $$$M$$$ строках описаны тропинки четырьмя целыми числами $$$u_i$$$, $$$v_i$$$, $$$s_i$$$ и $$$w_i$$$ — номера полянок, из которой и в которую ведёт тропинка, и количество грибов и ягод на этой тропинке в любой день $$$(1 \le u_i, v_i \le 10^5, u_i \neq v_i, 1 \le s_i, w_i \le 10^9)$$$.
В следующих $$$Q$$$ строках даны по два целых числа $$$a_j$$$ и $$$b_j$$$ — стоимость одного гриба и одной ягоды в $$$j$$$-й день $$$(1 \le a_j, b_j \le 10^9)$$$.
Гарантируется, что две различные тропинки не могут соединять одну и ту же пару полянок, а также что они не образуют цикл.
Выведите $$$Q$$$ строк. В $$$i$$$-й строке выведите «YES», если в $$$i$$$-й день мой дед смог пройти так, как он рассказывал, либо «NO» в противном случае.
3 3 3 1 2 2 4 2 3 3 9 1 3 10 50 58 9 60 23 61 9
YES NO YES
Вадим решил покорять новые просторы и начать писать рэп на старобарском. В старобарском языке $$$N$$$ слов, а в алфавите всего $$$26$$$ букв, для своего удобства Вадим запоминает их как латинские. В этом языке произносится каждая буква слова, а, значит, и рифмуются слова гораздо проще.
Однако, чтобы посчитать, насколько хорошо рифмуются два слова, нужно нехило заморочиться. Вадим выбирает суффикс одинаковой длины у двух слов, и они рифмуются на значение, равное этой длине и делённое на $$$2$$$ за каждое различие в каждой из соответствующих позиций. При этом Вадим может сам выбрать любую длину суффикса, поэтому два слова рифмуются на значение, максимальное для каждой пары суффиксов одинаковой длины.
Вадиму уже известны значения каждого из слов, поэтому осталось только написать текст в рифму. У него есть $$$Q$$$ вариантов, подходящих по смыслу для его трека. Чтобы звучать более в рифму, Вадим даже готов отрезать по нескольку букв с конца у обоих слов. Помогите начинающему рэперу, ответив для каждого варианта, насколько хорошо получится рифма из этих двух слов.
В первой строке даны два целых числа $$$N$$$ и $$$Q$$$ — количество слов в старобарском языке и количество вариантов, предложенных Вадимом $$$(2 \le N \le 10^5, 1 \le Q \le 10^5)$$$.
В следующих $$$N$$$ строках даны слова $$$s_i$$$ старобарского языка, состоящие из строчных латинских букв $$$(1 \le |s_i| \le 10^5)$$$.
В следующих $$$Q$$$ строках даны три целых числа $$$u_i$$$, $$$v_i$$$ и $$$c_i$$$ — два номера слов из старобарского языка в порядке ввода, которые содержатся в $$$i$$$-м варианте Вадима; и количество букв, которые он отрежет с конца у обоих слов $$$(1 \le u_i,v_i \le N, 0 \le c_i \lt \min(|s_{u_i}|, |s_{v_i}|))$$$.
Гарантируется, что общая длина всех слов не превосходит $$$10^6$$$ символов.
Выведите $$$Q$$$ чисел — насколько хороша рифма для каждого из вариантов в порядке ввода.
Ответ будет засчитан, если абсолютная или относительная погрешность значений не превосходит $$$10^{-6}$$$. Формально, пусть ваш ответ равен $$$x$$$, а ответ жюри равен $$$y$$$. Ваш ответ считается правильным, если $$$\frac{|x-y|}{\max (1,|y|)} \le 10^{-6}$$$.
5 7 fate cmake stake cfake cmate 1 2 0 2 3 0 1 4 0 2 5 0 1 5 0 1 4 1 2 5 2
1.5 3 2 2.5 3 1.5 3