У Василисы сегодня день рождения! Она позвала всех своих друзей в гости пить чай. Борис, как и полагается, хочет принести Василисе подарок, поэтому он купил $$$A$$$ замечательных квадратов со стороной $$$2$$$, а также $$$B$$$ прекрасных квадратов со стороной $$$1$$$. Осталось только найти подходящую упаковку в Бесконечном магазине.
Борис обнаружил, что в магазине есть много подарочных коробок. Вот только из соображений стандартизации ширина каждой коробки равна $$$K$$$. Но хоть в чём-то название магазина остаётся не просто маркетинговым ходом: таких коробок тут бесконечно много, и можно найти коробку любой целочисленной длины.
Борис очень просит вас помочь ему выбрать коробку ширины $$$K$$$ и минимальной длины, в которую он может положить все свои подарки так, чтобы стороны подарков были параллельны сторонам коробки.
Первая строка входных данных содержит целое число $$$A$$$ ($$$0 \le A \le 10^8$$$) — количество квадратов со стороной $$$2$$$.
Вторая строка содержит целое число $$$B$$$ ($$$0 \le B \le 10^8$$$) — количество квадратов со стороной $$$1$$$.
Третья строка содержит целое число $$$K$$$ ($$$2 \le K \le 10^8$$$) — ширину каждой коробки в магазине.
Гарантируется, что $$$A + B \gt 0$$$, то есть Василисе подарили хотя бы один квадрат.
Выведите одно число $$$X$$$ — минимальную длину коробки такую, что в коробку $$$K \times X$$$ вместятся все подаренные квадраты, уложенные параллельно сторонам коробки.
Решения, правильно работающие, когда числа $$$A$$$, $$$B$$$, $$$K$$$ не превосходят $$$100$$$, будут оцениваться в 35 баллов.
333
6
415
4
244
3
Возможные способы уложить квадраты для примеров из условия:
![]() | ![]() | ![]() |
| Пример 1 | Пример 2 | Пример 3 |
Во втором примере Василисе подарили $$$4$$$ квадрата со стороной $$$2$$$ (изображены на рисунке красным) и $$$1$$$ квадрат со стороной $$$1$$$ (изображен на рисунке жёлтым). Также известно, что ширина коробки (вертикальная сторона) равна $$$5$$$. Тогда минимальная длина (горизонтальная сторона) коробки, которая вмещает все квадраты, равна $$$4$$$. Пример расположения квадратов в такой коробке изображён на рисунке. Можно показать, что в коробку со стороной меньше $$$4$$$ все квадраты поместить нельзя.
На день рождения Василиса решила угостить выпечкой $$$N$$$ своих гостей. Она получила в местной пекарне промокод на $$$K$$$ рублей, но для его использования нужно выбрать выпечки ровно на $$$K$$$ рублей, иначе акция недействительна. В пекарне продаётся два вида товаров: кексы по $$$A$$$ рублей за штуку и печенье по $$$B$$$ рублей за штуку (при этом $$$A \ne B$$$). Василиса хочет купить ровно $$$N$$$ штук выпечки.
Определите, сможет ли она воспользоваться промокодом, и если сможет, то выведите количество кексов и печенья, которое ей нужно купить.
Первая строка входных данных содержит целое число $$$K$$$ ($$$1 \le K \le 10^{9}$$$) — номинал промокода в пекарне.
Вторая строка содержит целое число $$$N$$$ ($$$1 \le N \le 10^{9}$$$) — количество гостей Василисы.
Третья строка содержит целое число $$$A$$$ ($$$1 \le A \le 10^{9}$$$) — стоимость одного кекса.
Четвёртая строка содержит целое число $$$B$$$ ($$$1 \le B \le 10^{9}$$$) — стоимость одного печенья.
Гарантируется, что $$$A \ne B$$$.
Если существует набор выпечки, удовлетворяющий условию, то выведите два числа — количество кексов и количество печенья, которое должна купить Василиса, соответственно. Если же такого набора выпечки не существует, то выведите «$$$-1$$$» (без кавычек).
Решения, правильно работающие, когда значения $$$K$$$, $$$N$$$, $$$A$$$, $$$B$$$ не превосходят $$$10^{3}$$$, будут оцениваться в $$$30$$$ баллов.
Решения, правильно работающие, когда значения $$$K$$$, $$$N$$$, $$$A$$$, $$$B$$$ не превосходят $$$10^{6}$$$, будут оцениваться в $$$60$$$ баллов.
11351
2 1
15353
3 0
16354
-1
В первом примере Василисе нужно купить 3 единицы выпечки стоимостью 11 рублей. Она может купить 2 кекса по 5 рублей и 1 печенье по 1 рублю. $$$2 + 1 = 3$$$ и $$$2 \cdot 5 + 1 \cdot 1 = 11$$$
Родители подарили Василисе на день рождения «Икес Бокес Сирес Икес», на котором она решила поиграть в змейку. Игровое поле представляет собой прямоугольник из $$$n$$$ строк и $$$m$$$ столбцов.
Змейка длины $$$k$$$ состоит из $$$k$$$ сегментов, пронумерованных от $$$1$$$ до $$$k$$$ от головы к хвосту. Каждый сегмент занимает одну клетку поля. Изначально змейка имеет длину $$$1$$$ и занимает только верхнюю левую клетку поля (клетка в строке $$$1$$$ и столбце $$$1$$$).
Также в течение игры на поле появится $$$q$$$ яблок, причём изначально на поле есть только первое яблоко. $$$i$$$-е яблоко появляется на поле, когда змейка съедает яблоко $$$i-1$$$. Таким образом, до конца игры на поле в каждый момент находится ровно одно яблоко.
Пусть голова змейки находится в клетке в строке $$$i$$$ и столбце $$$j$$$. Тогда следующая клетка на пути змейки определяется так:
В течение игры каждую секунду происходит следующее.
Каждый раз, когда змейка съедает яблоко, на поле появляется следующее яблоко (если съеденное яблоко не было последним). Если яблоко появилось в клетке, которая в данный момент занята змейкой, то змейка съедает его в ту же секунду, не перемещаясь, и на поле появляется следующее яблоко. Если и последующие яблоки будут появляться в клетках, уже занятых змейкой, то все они будут съедены моментально. Для большей ясности изучите пояснения к примеру в разделе «Замечание».
Определите, за какое количество секунд змейка съест все $$$q$$$ яблок.
Можно показать, что не может возникнуть ситуация, в которой длина змейки станет больше $$$n \cdot m$$$.
В первой строке находятся три числа $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \le n, m, q \le 10^5$$$) — количество строк и количество столбцов игрового поля и количество яблок.
В $$$i$$$-й из следующих $$$q$$$ строк находятся два числа $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$) — номера строки и столбца клетки, в которой появляется $$$i$$$-е яблоко. Обратите внимание, что яблоко может появиться в той клетке, в которой яблоко уже было ранее.
Программа должна вывести одно число — количество секунд, через которое змейка съест все яблоки.
Обратите внимание, что ответ может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).
Решения, правильно работающие при $$$q = 1$$$, будут оцениваться в $$$20$$$ баллов.
Решения, правильно работающие при $$$n, m, q \le 200$$$, будут оцениваться в $$$50$$$ баллов.
2 3 41 32 22 11 1
6
2 2 41 11 21 21 1
1
2 4 41 31 41 12 4
8
В первом примере в поле $$$2$$$ строки, $$$3$$$ столбца, и в игре будет $$$4$$$ яблока. Игра закончится через $$$6$$$ секунд:
![]() | ![]() | ![]() |
| До начала игры | После первой секунды | После второй секунды |
Во вторую секунду змейка съела первое яблоко и стала на $$$1$$$ длиннее. Также на поле появилось второе яблоко.
![]() | ![]() |
| После третьей секунды | После четвёртой секунды |
В четвёртую секунду змейка съедает второе яблоко и увеличивает свою длину на $$$1$$$. Также третье яблоко появляется в клетке, в которой уже находится змейка, поэтому оно оказывается съедено моментально, а змейка не увеличивается. На поле появляется четвёртое яблоко.
![]() | ![]() |
| После пятой секунды | После шестой секунды |
После пятой секунды голова змейки находится в клетке $$$(2;3)$$$, поэтому следующей клеткой на её пути будет клетка $$$(1;1)$$$. Голова змейки перемещается в неё и змейка съедает последнее (четвёртое) яблоко.
Во втором примере в момент начала игры змейка съест яблоко в клетке $$$(1;1)$$$ (это произойдёт моментально). Далее, в первую секунду змейка съест яблоко в клетке $$$(1;2)$$$, и её голова переместится в эту клетку. В эту же секунду второе яблоко появится в клетке, в которой сейчас находится голова, и окажется съедено. Третье яблоко также будет съедено моментально, так как в клетке $$$(1;1)$$$ находится второй сегмент змейки.
В денежной системе Древнего Египта было $$$n$$$ различных типов монет. Курс обмена монет полностью стабилен. Монеты пронумерованы по ценности от $$$1$$$ до $$$n$$$: монета $$$1$$$ является наименее ценной, а монета $$$n$$$ — наиболее ценной. А именно: $$$a_i$$$ монет типа $$$i$$$ равноценны одной монете типа $$$i+1$$$, для всех $$$1 \le i \le n-1$$$ (известно, что $$$a_i \geq 2$$$). Также можно производить несколько обменов, то есть $$$1$$$ монета типа $$$3$$$ по стоимости равна $$$a_1 \cdot a_2$$$ монетам типа $$$1$$$. Можно как менять более ценные монеты на менее ценные, так и наоборот.
Сегодня у Василисы день рождения. В подарок она получила набор древнеегипетских монет. В наборе содержится $$$b_1$$$ монет типа $$$1$$$, $$$b_2$$$ монет типа $$$2$$$, ..., $$$b_n$$$ монет типа $$$n$$$.
Чтобы помочь Василисе оценить её богатство, она просит вас обработать $$$q$$$ запросов. Запросы бывают двух типов:
В первой строке входных данных содержится единственное целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество различных монет в денежной системе Древнего Египта.
Во второй строке входных данных содержатся $$$n - 1$$$ целых чисел: $$$a_1, a_2, \ldots, a_{n-1}$$$ ($$$2 \le a_i \le 10^9$$$) — $$$a_i$$$ обозначает количество монет типа $$$i$$$, которое равно по стоимости одной монете типа $$$i + 1$$$.
В третьей строке входных данных содержатся $$$n$$$ целых чисел: $$$b_1, b_2, \ldots, b_{n}$$$ ($$$0 \le b_i \le 10^9$$$) — первоначальное количество монет каждого типа в наборе Василисы.
В четвёртой строке входных данных содержится единственное целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.
В следующих $$$q$$$ строках содержатся запросы, по одному в строке. Каждый запрос состоит из трёх чисел $$$t, x, y$$$ ($$$1 \le t \le 2, 1 \le x \le 10^9, 1 \le y \le n$$$). Если $$$t = 1$$$, Василиса добавляет в свой набор $$$x$$$ монет типа $$$y$$$. Если $$$t = 2$$$, вам нужно сравнить стоимость всего текущего набора Василисы со стоимостью $$$x$$$ монет типа $$$y$$$.
Для каждого запроса типа $$$2$$$ в отдельной строке выведите $$$1$$$, если стоимость набора Василисы не меньше стоимости $$$x$$$ монет типа $$$y$$$. Если это неверно, то выведите число $$$0$$$.
Помимо тестов из условия, в этой задаче $$$50$$$ тестов, каждый из которых оценивается в $$$2$$$ балла.
Гарантируется, что:
52 4 5 3120 60 15 3 1142 600 12 601 12 75 32 76 31 3 21 1 12 76 31 1 12 76 31 1000000000 12 10000000 42 10000000 51 999999777 12 1000000000 2
1 0 1 0 0 1 1 0 1
В примере из условия есть $$$5$$$ типов монет. Одна монета типа $$$2$$$ стоит как $$$2$$$ монеты типа $$$1$$$, одна монета типа $$$3$$$ стоит как $$$8$$$ монет типа $$$1$$$, одна монета типа $$$4$$$ стоит как $$$40$$$ монет типа $$$1$$$, и одна монета типа $$$5$$$ равноценна $$$120$$$ монетам типа $$$1$$$.
Первоначально у Василисы есть $$$120$$$ монет типа $$$1$$$, $$$60$$$ монет типа $$$2$$$, $$$15$$$ монет типа $$$3$$$, $$$3$$$ монеты типа $$$4$$$ и $$$1$$$ монета типа $$$5$$$. В пересчёте на монеты типа $$$1$$$ монеты Василисы имеют ценность эквивалентную $$$600$$$ монетам типа $$$1$$$. В пересчёте на монеты типа $$$3$$$ — ценность монет Василисы эквивалентна $$$75$$$ монетам типа $$$3$$$. Это даёт ответы на первые четыре запроса.
В пятом запросе добавляется $$$3$$$ монеты типа $$$2$$$. В шестом запросе добавляется $$$1$$$ монета типа $$$1$$$. После этого суммарная ценность монет эквивалентна $$$600 + 2 \cdot 3 + 1 = 607$$$ монетам типа $$$1$$$. При этом $$$76$$$ монет типа $$$3$$$ равноценны $$$608$$$ монетам типа $$$1$$$, поэтому ответом на седьмой запрос будет $$$0$$$.
В восьмом запросе добавляется ещё одна монета типа $$$1$$$, и после этого ценность монет Василисы в точности эквивалентна $$$76$$$ монетам типа $$$3$$$, и ответом на девятый запрос будет $$$1$$$.