Придя домой, уставший Константин захотел выпить свой любимый чай. Для этого ему нужно было достать с высокой полки самое красивое блюдце, которое представляет собой клетчатое поле $$$N \times N$$$. Но, так как Константин не очень аккуратен, он блюдце разбил.
В спешке Костя начал думать, как же починить столь ценную вещь. И тогда он заметил, что блюдце распалось ровно на клетчатые квадраты $$$K \times K$$$! Более того он обнаружил, что $$$N$$$ делится на $$$K$$$ без остатка.
Восстановив исходное блюдце из кусочков, Костя понял, что ему также нужно купить клей, чтобы склеить все соприкасающиеся кусочки в исходное клетчатое поле $$$N \times N$$$. Он тут же посчитал, что, для того чтобы проклеить границу между двумя соприкасающимися клетками длины $$$1$$$, необходима ровно одна банка клея.
Помогите Косте посчитать, сколько банок клея ему нужно купить, чтобы склеить его любимое блюдце.
В первой строке входных данных записано одно целое число $$$N$$$ ($$$1 \leq N \leq 10^4$$$) — размер квадратного блюдца.
Во второй строке записано одно целое число $$$K$$$ ($$$1 \leq K \leq N$$$, $$$N$$$ делится на $$$K$$$ без остатка) — размер квадратного осколка блюдца.
В единственной строке выведите одно число — количество банок клея, которые Косте понадобится купить, чтобы починить блюдце.
Если на самом деле блюдце не разбилось, и Костя зря паниковал, выведите число $$$0$$$.
Решения, правильно работающие только для случаев, когда $$$N$$$ и $$$K$$$ не превосходят $$$20$$$, будут оцениваться в $$$25$$$ баллов.
Решения, правильно работающие только для случаев, когда $$$K = 1$$$, будут оцениваться в $$$30$$$ баллов.
2 1
4
3 3
0
Рисунок ниже иллюстрирует первый пример:
Различными цветами обозначены различные части блюдца, изначально имевшего размер $$$2 \times 2$$$. Между частями белым цветом обозначен клей, который Костя купил и намазал, чтобы починить блюдце. Каждая часть блюдца имеет размер $$$1 \times 1$$$.
Во втором тестовом примере Костя зря паниковал, и на самом деле он не разбил блюдце!
Персонаж известной компьютерной игры Марио постарел и почти перестал прыгать. Но совсем недавно он увидел спуск из $$$N$$$ ступенек, и его накрыло ностальгией. Марио встал на самую верхнюю ступеньку и решил преодолеть этот спуск при помощи прыжков.
Когда-то Марио знал тысячи различных видов прыжков, но теперь он смог вспомнить только два: короткие и длинные. Короткий прыжок позволяет спуститься на произвольное число ступенек, не большее $$$X$$$, а длинный — на произвольное число, не большее $$$Y$$$ ($$$X \lt Y$$$). Но в силу возраста Марио не может делать два длинных прыжка подряд и вынужден между ними совершать хотя бы один короткий. При этом Марио не хочет слишком уж сильно ухудшить свои прошлые результаты и поэтому постарается обойтись как можно меньшим числом прыжков.
Помогите Марио посчитать минимальное количество прыжков, требующееся для преодоления всех $$$N$$$ ступенек.
В первой строке входных данных записано целое число $$$X$$$ — максимальная длина короткого прыжка.
Во второй строке записано целое число $$$Y$$$ ($$$1 \leq X \lt Y \leq 10^{18}$$$) — максимальная длина длинного прыжка.
В третьей строке записано целое число $$$N$$$ ($$$1 \leq N \leq 10^{18}$$$) — количество ступенек в спуске.
В единственной строке выведите целое число — минимальное число прыжков, необходимое Марио для спуска.
Решения, правильно работающие только для случаев, когда $$$X$$$, $$$Y$$$ и $$$N$$$ не превосходят $$$10^5$$$, будут оцениваться в $$$35$$$ баллов.
Решения, правильно работающие только для случаев, когда $$$X$$$, $$$Y$$$ и $$$N$$$ не превосходят $$$10^9$$$, будут оцениваться в $$$50$$$ баллов.
2 3 5
2
1 2 4
3
1 100 1000000000000000000
19801980198019801
На изображениях ниже приведены возможные способы решения первых двух тестов из условия:
Обратите внимание, что входные данные, а также ответ могут быть достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.
Андрей вот-вот опоздает на школьный этап ВсОШ. К счастью, недавно в его городе появились порталы.
Город, в котором живет Андрей, можно представить в виде прямой. Всего в городе успели построить $$$N$$$ порталов. Портал с номером $$$i$$$ расположен в точке с координатой $$$x_i$$$. Если в текущий момент времени вы находитесь в одной точке с каким-нибудь порталом, то можете всего за одну секунду телепортироваться в любой другой портал вне зависимости от расстояния между ними. А время, требуемое для преодоления расстояния между точками с координатами $$$p$$$ и $$$q$$$ без использования порталов равно $$$\lvert p - q \rvert$$$ секунд. Андрей является влиятельным гражданином, поэтому он может использовать систему порталов любое количество раз.
Изначально Андрей находится в точке $$$s$$$, а точка проведения олимпиады имеет координату $$$e$$$. Помогите Андрею понять, как быстро он может попасть на олимпиаду, ведь каждая секунда на счету.
В первой строке входных данных записано одно целое число $$$s$$$ — начальное положение Андрея.
Во второй строке записано одно целое число $$$e$$$ — место проведения олимпиады.
В третьей строке записано количество порталов $$$N$$$ ($$$2 \le N \le 2 \cdot 10^5$$$).
В каждой из $$$N$$$ следующих строк записано целое число $$$x_i$$$ — координата портала с номером $$$i$$$.
Все числа $$$s$$$, $$$e$$$, $$$x_i$$$ по модулю не превосходят $$$10^8$$$.
Выведите одно число — минимальное количество секунд, которое потребуется Андрею для того, чтобы добраться до места проведения олимпиады.
Решения, правильно работающие только для случаев, когда $$$N$$$ не превосходит $$$10$$$, будут оцениваться в $$$20$$$ баллов.
Решения, правильно работающие только для случаев, когда $$$N$$$ не превосходит $$$1\,000$$$, будут оцениваться в $$$60$$$ баллов.
0 4 3 1 3 5
3
Рассмотрим пример из условия.
Если бы Андрей не мог пользоваться порталами, он бы смог добраться до точки проведения олимпиады за $$$\lvert 0 - 4 \rvert = 4$$$ секунды. Однако, можно действовать так:
Суммарно получаем $$$1 + 1 + 1 = 3$$$ секунды.
Горилла Коко очень любит путешествовать по своим родным джунглям с помощью лиан.
Всего в джунглях есть $$$N$$$ лиан, расположенных друг за другом и пронумерованных слева направо целыми числами от $$$1$$$ до $$$N$$$. Расстояние между соседними лианами составляет $$$D$$$ метров. Находясь на $$$i$$$-й лиане, Коко может совершить прыжок с нее не более, чем на $$$a_i$$$ метров вправо. В процессе прыжка Коко должна зацепиться за какую-то другую лиану, мимо которой будет пролетать.
В данный момент Коко висит на первой лиане и хочет переместиться как можно дальше вправо. Помогите Коко и определите максимальный номер лианы, до которой она сможет добраться.
Первая стока входных данных содержит целое число $$$N$$$ ($$$2 \leq N \leq 10^{5}$$$) — количество лиан.
Во второй строке записано целое число $$$D$$$ ($$$1 \leq D \leq 10^{9}$$$) — расстояние между соседними лианами.
В каждой из следующих $$$N$$$ строк записано целое число $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — на сколько метров вправо может прыгнуть Коко, находясь на $$$i$$$-й лиане.
Выведите единственное целое число — максимальный номер лианы, до которой сможет добраться Коко.
Решения, работающие при $$$N \leq 15$$$, будут набирать не менее $$$16$$$ баллов.
Решения, работаюшие при $$$D = 1$$$, будут набирать не менее $$$12$$$ баллов.
Решения, работающие при $$$N \leq 2000$$$, будут набирать не менее $$$56$$$ баллов.
5 3 7 8 2 2 6
4
В примере из условия дано 5 лиан, а расстояние между лианами равно 3 метрам. Находясь на первой лиане, Коко может прыгнуть не более, чем на 7 метров, то есть она сможет допрыгнуть до второй и третьей лианы. Ей нужно остановиться на второй лиане, потому что со второй лианы длина прыжка равна 8 метрам, и это позволит ей допрыгнуть до четвёртой лианы. С четвёртой лианы длина прыжка равна 2 и это меньше, чем расстояние до следующей лианы, поэтому Коко остановится на четвёртой лиане.
Однажды после олимпиады по экономике Мише приснился очень красочный и необычный сон. Мальчик оказался министром финансов Берляндии. Осознав свою значимость, он тут же решил произвести в стране реформу. Раньше в Берляндии использовались банкноты с номиналами $$$1$$$, $$$10$$$, $$$100$$$ и $$$1\,000$$$ бурлей. Мише данная система показалась крайне банальной, поэтому он решил придумать что-то свое.
Мальчик выбрал два целых числа $$$x$$$ и $$$y$$$ ($$$x \leq y$$$) и заявил, что теперь в Берляндии будут использоваться только банкноты с номиналами $$$x,~x + 1,~x + 2,~\ldots,~y$$$ бурлей. Вскоре реформа была принята и вступила в силу, однако населению страны это совсем не понравилось. Недовольства начались из-за того, что теперь, используя новые банкноты, можно было набрать далеко не любую сумму.
Например, если Мишей были выбраны числа $$$x = 5$$$ и $$$y = 7$$$, то невозможно набрать суммы $$$1$$$, $$$2$$$, $$$3$$$ и $$$4$$$ бурлей. Также не получится набрать суммы $$$8$$$ и $$$9$$$ бурлей. Если же выбрать числа $$$x = y = 2$$$, то невозможно будет набрать любую нечетную сумму.
Миша, находясь на грани увольнения, решил успокоить население Берляндии и предъявить такое минимальное число $$$N$$$, что при помощи новых банкнот возможно набрать любую сумму, начиная с $$$N$$$. Таким образом, должно быть возможно набрать суммы $$$N$$$ бурлей, $$$N + 1$$$ бурлей, $$$N + 2$$$ бурлей, и так далее. Помогите Мише найти искомое число $$$N$$$ и избежать увольнения.
В первой строке входных данных записано целое число $$$x$$$ — минимальный номинал новых банкнот.
Во второй строке записано целое число $$$y$$$ ($$$1 \leq x \leq y \leq 2 \cdot 10^9$$$) — максимальный номинал новых банкнот.
Выведите одно натуральное число $$$N$$$ — минимальное число, такое, что при помощи банкнот с номиналами $$$x,~x + 1,~x + 2,~\ldots,~y$$$ можно набрать любую сумму, начиная с $$$N$$$ бурлей.
Если такого числа не существует, в качестве ответа выведите $$$-1$$$.
Решения, правильно работающие только для случаев, когда $$$x$$$ и $$$y$$$ не превосходят $$$10^4$$$, будут оцениваться в $$$40$$$ баллов.
5 7
10
2 2
-1
1900000000 2000000000
36100000000
В первом примере имеются банкноты трех номиналов: $$$5, 6$$$ и $$$7$$$ бурлей. Ниже перечислены суммы, которые можно набрать при помощи данных банкнот:
Можно показать, что при помощи банкнот данных номиналов возможно набрать любую сумму, начиная с $$$10$$$ бурлей.
Во втором примере есть банкноты всего одного номинала: $$$2$$$ бурля. При помощи данных банкнот можно набрать только любую чётную сумму: 2, 4, 6, .... Таким образом, искомого числа $$$N$$$ не существует.
Обратите внимание, что ответ может получиться достаточно большим, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.