У Тимофея есть три палочки с натуральными длинами $$$a$$$, $$$b$$$ и $$$c$$$, из которых можно сложить треугольник. За одну операцию мальчик отламывает от каждой палочки по кусочку единичной длины. Спустя какое минимальное количество операций из палочек уже нельзя будет сложить треугольник?
Для определённости считайте, что от палочки единичной длины можно отломить кусок длины 1, после чего палочка исчезнет.
Три строки входного файла содержат три натуральных числа $$$a$$$, $$$b$$$ и $$$c$$$ ($$$1 \le a, b, c \le 10^{9}$$$). Гарантируется неравенство треугольника для указанных длин.
Выведите одно натуральное число – ответ на вопрос задачи.
Решения, правильно работающие, когда числа $$$a$$$, $$$b$$$ и $$$c$$$ равны, будут оцениваться в 10 баллов.
Решения, правильно работающие, когда числа $$$a$$$, $$$b$$$ и $$$c$$$ не превосходят $$$10^{5}$$$, будут оцениваться в 40 баллов.
10 18 12
4
В примере дано $$$a = 10$$$, $$$b = 18$$$ и $$$c = 12$$$. Три операции спустя длины сторон окажутся равны 7, 15 и 9 (треугольник можно сложить в последний раз). А вот после четвёртой операции длины палочек составят 6, 14 и 8, и треугольник окажется вырожденным.
Поверхность куба со стороной $$$n$$$ см покрасили снаружи в синий цвет (со всех шести сторон). После этого его распилили на кубики со стороной 1 см. В результате получились части, у которых синим цветом окрашены 0, 1, 2 или 3 стороны. Посчитайте количество кубиков указанного вида.
Первая строка содержит натуральное число $$$n$$$ ($$$2 \le n \le 1000$$$) – размер кубика.
Вторая строка содержит неотрицательное целое число $$$f$$$ ($$$0 \le f \le 3$$$) – количество окрашенных граней у кубиков, число которых нужно посчитать.
Выведите одно неотрицательное целое число – ответ на вопрос задачи. Гарантируется, что оно не превосходит $$$10^9$$$.
Решения, правильно работающие, когда число $$$f$$$ равно 0, будут оцениваться в 30 баллов.
Решения, правильно работающие, когда число $$$f$$$ равно 1, будут оцениваться в 30 баллов.
Решения, правильно работающие, когда число $$$f$$$ равно 2, будут оцениваться в 30 баллов.
Решения, правильно работающие, когда число $$$f$$$ равно 3, будут оцениваться в 10 баллов.
3 1
6
В примере дано $$$n = 3$$$ и $$$f = 1$$$. Рассмотрим рисунок: куб $$$3 \times 3 \times 3$$$ покрасили и распилили на $$$3^3 = 27$$$ маленьких кубиков. Требуется определить, сколько таких кубиков имеют единственную синюю грань.
Это кубики, расположенные посередине каждой из шести граней, их ровно шесть.
На лето родители отправили Антона к бабушке помогать ей выращивать в огороде арбузы. Чтобы они выросли большими и вкусными, требуется поливать растения каждый день, что и было поручено мальчику. Если арбуз был полит, он вырастает на один килограмм (а если не был, то остаётся прежнего размера) за каждый день.
Сам огород представляет собой прямоугольную сетку из $$$n$$$ строк и $$$m$$$ столбцов, в каждой ячейке которой растёт арбуз, изначально имеющий массу 0 килограмм. Антон очень не любит работать, поэтому в $$$i$$$-й день из всех $$$d$$$, что он будет гостить у бабушки, планирует поливать только арбузы, лежащие на пересечении первых $$$x_i$$$ строк и первых $$$y_i$$$ столбцов.
В конце лета за свою работу мальчик получит самый большой арбуз из имеющихся в огороде (а если их несколько, то сразу все самые большие!). Антон очень любит гигантские арбузы, поэтому просит вас определить, сколько же их в итоге ему достанется, и какого они будут веса.
Первые три строки входных данных содержат целые числа $$$n$$$, $$$m$$$ и $$$d$$$ именно в таком порядке — количество строк и столбцов в огороде и время пребывания Антона у бабушки $$$(1 \leqslant n, m \leqslant 10^9$$$, $$$1 \leqslant d \leqslant 10^5)$$$. Далее идут $$$2d$$$ чисел $$$x_i$$$ и $$$y_i$$$, каждое в отдельной строке, обозначающих количество строк и столбцов, арбузы в которых были политы мальчиком в день номер $$$i$$$ $$$(1 \leqslant x_i \leqslant n, 1 \leqslant y_i \leqslant m)$$$. Уточним, что эти данные упорядочены по дням, т.е. сначала идёт пара чисел $$$x_1$$$, $$$y_1$$$, именно в таком порядке, затем $$$x_2$$$, $$$y_2$$$ и так далее.
Отметим отдельно, что бабушка пронумеровала все строки и столбцы в огороде, и Антон всегда поливает именно $$$x_i$$$ первых строк и $$$y_i$$$ первых столбцов.
$$$\textbf{Обратите внимание}$$$, что при заданных ограничениях для хранения ответов необходимо использовать $$$64$$$-битный тип данных, например $$$\textbf{long}$$$ $$$\textbf{long}$$$ в $$$\textbf{C++}$$$, $$$\textbf{int64}$$$ в $$$\textbf{Free}$$$ $$$\textbf{Pascal}$$$, $$$\textbf{long}$$$ в $$$\textbf{Java}$$$.
Выведите два числа через пробел — количество арбузов, которые достанутся Антону, и вес каждого из них.
Решения, правильно работающие, когда произведение чисел $$$n$$$, $$$m$$$ и $$$d$$$ не превосходит $$$10^6$$$, будут оцениваться в 50 баллов.
3 3 1 2 2
4 1
4 3 2 3 1 1 2
1 2
В первом примере Антон один раз поливает квадрат $$$2 \times 2$$$, поэтому ему достанется 4 арбуза массой 1 килограмм каждый.
Во втором примере будут политы 3 арбуза в первом столбце и 2 арбуза в первой строке. Тогда ровно один арбуз окажется полит дважды, его Антон и получит.
Платные музыкальные сервисы предлагают самый разный контент за любые деньги, но работают по одному и тому же принципу: за первый месяц подписки клиент платит $$$a$$$ рублей, а далее, за каждый следующий месяц подписки, ещё $$$d$$$ рублей. Таким образом, за $$$n$$$ месяцев клиент заплатит $$$a + (n - 1) \cdot d$$$ рублей. Известно, что для любых натуральных $$$a$$$ и $$$d$$$ существует ровно один сервис, который предлагает свои услуги именно на таких условиях.
У Тимофея есть $$$m$$$ рублей, и ему требуется подключить ровно один сервис. Он хочет выяснить, на скольких из них он может получать за эти деньги доступ к музыке в течение $$$n$$$ месяцев. Если денег хватит на количество месяцев, превышающее $$$n$$$, Тимофея такой сервис тоже устроит.
На вход подаются два натуральных числа $$$n$$$ ($$$2 \le n \le 10^{6}$$$) и $$$m$$$ ($$$1 \le m \le 10^{6}$$$), каждое в своей строке.
Обратите внимание, что при заданных ограничениях для хранения ответа может понадобиться $$$64$$$-битный тип данных, например long long в C++, int64 в Pascal, long в Java.
Выведите одно неотрицательное целое число – количество различных сервисов, на которых Тимофей может $$$n$$$ месяцев получать доступ к музыке, заплатив при этом не более $$$m$$$ рублей.
Решения, правильно работающие, когда число $$$m$$$ не превосходит $$$2$$$, получат не менее 10 баллов.
Решения, правильно работающие, когда число $$$m$$$ не превосходит $$$1000$$$, получат не менее 50 баллов.
3 7
9
В примере из условия у Тимофея есть 7 рублей, и он хочет слушать музыку 3 месяца. Тогда ему подойдут следующие сервисы:
$$$a = 1,\ d = 1$$$ (он заплатит в сумме 1 + 2 $$$\cdot$$$ 1 = 3 рубля)
$$$a = 2,\ d = 1$$$ (он заплатит в сумме 2 + 2 $$$\cdot$$$ 1 = 4 рубля)
$$$a = 3,\ d = 1$$$ (он заплатит в сумме 3 + 2 $$$\cdot$$$ 1 = 5 рублей)
$$$a = 4,\ d = 1$$$ (он заплатит в сумме 4 + 2 $$$\cdot$$$ 1 = 6 рублей)
$$$a = 5,\ d = 1$$$ (он заплатит в сумме 5 + 2 $$$\cdot$$$ 1 = 7 рублей)
$$$a = 1,\ d = 2$$$ (он заплатит в сумме 1 + 2 $$$\cdot$$$ 2 = 5 рублей)
$$$a = 2,\ d = 2$$$ (он заплатит в сумме 2 + 2 $$$\cdot$$$ 2 = 6 рублей)
$$$a = 3,\ d = 2$$$ (он заплатит в сумме 3 + 2 $$$\cdot$$$ 2 = 7 рублей)
$$$a = 1,\ d = 3$$$ (он заплатит в сумме 1 + 2 $$$\cdot$$$ 3 = 7 рублей)
Таким образом, для данного примера у Тимофея есть возможность выбора из 9 музыкальных сервисов.
Близнецам Петру и Павлу родители подарили на день рождения настольный футбол, но не простой, а линейный.
В этом варианте игры все фигурки игроков расположены в одну линию на равном расстоянии друг от друга. Всего есть $$$n$$$ игроков. Для определенности пронумеруем их позиции числами от $$$1$$$ до $$$n$$$ слева направо. Ворота находятся в позициях $$$0$$$ и $$$n + 1$$$. Каждый игрок имеет свою силу удара, и может при ударе по мячу перебросить его на фиксированное количество позиций другому игроку. Силу удара игрока на позиции $$$i$$$ обозначим через $$$a_i$$$, что означает, что после удара этого игрока мяч переместится на $$$a_i$$$ позиций. Если $$$a_i$$$ положительное, то мяч переместится вправо, в сторону увеличения номеров, а если $$$a_i$$$ отрицательное, то мяч переместится влево, в сторону уменьшения. Если после удара мяч попадает в позицию меньшую либо равную $$$0$$$, то засчитывается гол в левые ворота, а если в позицию большую либо равную $$$n + 1$$$, то в правые. Если после удара мяч попадает к другому игроку, то тот наносит следующий удар со своей силой, и игра продолжается.
Близнецы решили сыграть $$$n$$$ игр, в $$$i$$$-й из которых первый удар нанесёт игрок номер $$$i$$$. Для каждой игры выведите, в какие ворота будет забит мяч в этой игре (L, если в левые, R, если в правые, U, если гол никто не забьёт).
Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \leqslant n \leqslant 10^5$$$) — количество игроков. Далее в следующих $$$n$$$ строках указаны силы и направления ударов игроков. В $$$i + 1$$$ строке указана сила игрока $$$a_i$$$, находящегося в позиции $$$i$$$. После удара этого игрока мяч окажется в позиции $$$i + a_i$$$. ($$$-10^5 \leqslant a_i \leqslant 10^5$$$ для любого $$$i$$$ от $$$1$$$ до $$$n$$$).
Выведите $$$n$$$ символов, обозначающих результаты игр, в одну строку без пробелов. Если пронумеровать эти символы от $$$1$$$ до $$$n$$$, то в $$$i$$$-й позиции этой строки должен находиться символ L для мяча, забитого в левые ворота, R для мяча, забитого в правые ворота, и U для случая, когда игра не закончилась взятием ворот (при начале этой игры c удара $$$i$$$-го игрока).
Решения, правильно работающие для случаев, в которых количество игроков не превосходит 100, получат не менее 44 баллов.
Решения, правильно работающие для случаев, в которых все игроки, кроме самого правого ударяют вправо, получат не менее 12 баллов.
Решения, правильно работающие для случаев, в которых левая половина игроков ударяет вправо, а правая половина игроков ударяет влево, причём количество игроков, перебрасывающих мяч на противоположную половину поля не превосходит 10, получат не менее 12 баллов.
Решения, правильно работающие для случаев, в которых каждая игра заканчивается взятием ворот, получат не менее 12 баллов.
10 -5 2 0 5 5 -1 6 -1 -1 -5
LRURUURRRU
В примере первый игрок сразу забивает в левые ворота. Второй игрок передаёт четвёртому, четвёртый — девятому, девятый — восьмому, восьмой — седьмому, а седьмой забивает в правые ворота. Третий игрок играет сам с собой. Пятый и десятый перекидывают мяч друг другу. Шестой передает пятому и далее снова играют пятый и десятый.
